I am additionally having this problem with a server running Ubuntu 8.04 and the client running Ubuntu 8.04. I am using the latest nfs-common and portmap. Even after attempting the solution proposed by Owen PG, I still had no success. If any additional information is required please don't hesitate to ask. Also I should mention both computers have ufw enabled with nfs forwarded on both.