Hi knaries2000, hi naesyllek!
I had exactly the same problem. The interresting thing in my case is: It was already working before.
We had to switch our whole network to another ipaddress range. After that we realized, that our backup wasn't working correct because the connection via nfs couldn't be established.
I checked everything (hosts.allow, hosts.deny, possibly set firewall rules, ...) without any success.
At last I had a look at the hosts file of both of the servers and there was the problem. We just forgot to modify those two machines.
On the client: Try to ping the server using the full qualified domain name (myclient.network.company.com) not the IPaddress
On the server: ping the client the same way.
They must know and reach each other.
In my case they don't, till I corrected my hosts-file.
In your case, check your dns configuration as well.
Hope it helps
PS: Sorry about my awful english