There is one possible reason for this error that has not been discussed here. And that is if PHP is configured to run in SAFE MODE.
When PHP runs in SAFE MODE it is blocks all attempts for php scripts to access files that are owned by another user than the executing script.
To allow the uploads there are two possibilities:
1. Set safe_mode = Off in php.ini (this will severly lower the security level of your php installation).
2. Set safe_mode_gid=On in php.ini
setup the upload directory with sticky bits: chmod 7777 wp-content/uploads
If you’re using the year/month setup set the sticky bits on the year-folders aswell. Make sure that the group on all the folders is the same as the owner of the php-scripts (normally the user account).
Hope this helps…