I had this problem ages ago but I can't remember exactly why...
things to double check:
/etc/exports - try using ip addresses instead of hostnames?
/etc/hosts.allow - add "portmap: hostname" for each host?
/etc/hosts.deny - make sure you don't have "ALL: ALL" or similar
/etc/hosts.equiv - mine has the entry "localhost"
also check iptables (firewall) configuration
sorry I can't be of more help