From everything I can see it looks like your permissions are set correctly. Apache2 is also set up correctly:
export APACHE_RUN_USER=www-data
export APACHE_RUN_GROUP=www-data
So I don't know what might be the trouble. If you have a spare laptop or old machine (or a empty partition on one), you could download and install from the LiveDVD --- it only takes 7 quick steps. That will give you Ubuntu 10.04.2 and you can check that uploads work. Then upgrade to 10.04.3 and check again. If things still work, I guess you can then try to see what is different on your server.
The LiveDVD is at the address above.
Arnie