Out of curiosity, what OS is this running on? As a sort of blind stab in the dark, I'd say having permissions at 0666 should be good enough, but I've run into similar problems with permissions myself. If the script is called by Apache, it's probably run as nobody - which will first require that nobody can write to the target directory. You might also consider explicitly chmod'ing the files to 0766 after you've written them - although this shouldn't be neccesary since generally who/whatever creates a file should own it.
in reply to running cgi as user other than nobody