I know this comes too late, but I have encountered a very rare scenario where I have virtual machines all using VMware with NAT enabled for the network adapters.

Slackware, RedHat, and Knoppix machines could all connect to a virtual Slackware NFS server, but Ubuntu clients could not. I had already checked the following file:
/etc/exports /etc/hosts.deny /etc/hosts.allow

And had already restarted NFS via:
sudo sh /etc/rc.d/rc.nfsd restart

I also checked that the mounts were available via:
showmount -e

I work on a large network, so I give access to the entire /16 subnet.
#[/etc/exports]
/mnt/my_shared_folder 192.168.0.0/255.255.0.0(rw,no_root_squash,no_subtree_check,sync)
#[/etc/hosts.deny]
portmap:ALL
lockd:ALL
mountd:ALL
rquotad:ALL
statd:ALL

#[/etc/hosts.deny]
portmap:192.168.0.0/255.255.0.0
lockd:192.168.0.0/255.255.0.0
mountd:192.168.0.0/255.255.0.0
rquotad:192.168.0.0/255.255.0.0
statd:192.168.0.0/255.255.0.0

This should have effectively allowed any host with an IP address beginning with 192.168.xxx.yyy to connect to my server. I have even tested this, yet for some reason, the Ubuntu client would not connect until I reduced my subnet from a Class B (/16) to a Class C (/24) range, like so:
#[/etc/exports]
/mnt/my_shared_folder 192.168.1.0/255.255.255.0(rw,no_root_squash,no_subtree_check,sync)

#[/etc/hosts.deny]
portmap:192.168.1.0/255.255.255.0
lockd:192.168.1.0/255.255.255.0
mountd:192.168.1.0/255.255.255.0
rquotad:192.168.1.0/255.255.255.0
statd:192.168.1.0/255.255.255.0

I don't know why it is only the Ubuntu VM that requires this obscure workaround, but at least it works.