Although I haven't tried it under a Fedora Core 2 OS, it's very strange that both zip alternatives (to use zip executables and to use Moodle internal zip libraries) throw you the same error.
When your backup fails, in your moodle_data/temp/backup an "CCCCCCCC" dir must be present (at least). That dirs are time-ordered. Select the last.
Can you try to zip it manually (from the shell)? Does it work? Any error (or output)?
Ciao