Really seems to be the permissions. There should be a user for php (it's not named php) but php runs under some user name (sorry for not being specific, I'm not a *nix guru).
Well, if you can't get it going, set the permissions to 0777 then. It's not very secure, but you can move the upload directory out from the web server root, so it's not accessible in public, to improve the security.