On Debian Squeeze, I created an NFS share with these options rw,sync,no_root_squash,no_subtree_check,insecure and on the other Debian Squeeze I can successfully mount it and read write with root, but this share is intended to be used by Apache. I changed the permission to 777 just to make sure. And still, the www-data user can read, create files but not write to them! It does not sound to me like the typical permissions problem, maybe something related to NFS, a lock problem that I am not aware of. Any idea is welcome.
I wouldn't use the sync option with a NFS share. Also, check if you need any extra apparmor permissions for apache, in /etc/apparmor.d/