if you look at phpinfo() on your site, you'll see an entry called 'safe-mode'
AFAIK, if this is set to 'on', then you can't do uploads. Basically you'll be trying to copy/move a file owned by userid xxx (perhaps 'nobody', the web user) in the temp file area to a directory owned by you, and it will squeal.
I got this error on one of my websites. Funny, I could upload via a perl script so having safe-mode set on seemed irrelevant unless it has another purpose.
Maybe someone more knowledgeable could comment.
Martin