… but everything is set up properly. Check if there is anything under /proc/fs/nfsd/. If there isn’t, run
# mount -t nfsd nfsd /proc/fs/nfsd
Apparently it happens when NFS support has been compiled into the kernel, but the userland tools have been built on a kernel where NFS is loaded as a module.
Another possible issue is if the server can’t resolve the client’s hostname. Might depend on NFS version. The client sends it’s hostname with the request, if the server can’t resolve it because it doesn’t have access to a DNS server for example, it might not allow the client to mount. First obvious solution is to make sure DNS resolution works properly, second obvious solution is to add the host to server’s /etc/hosts file. Third solution is less obvious, make sure there is no DNS server to interrogate. If there is nothing in resolv.conf to time out, the server will allow the connection, even if it can’t resolve the hostname.