So of course I have to ask...

What version of NFS are you running, and are you disallowing the older versions?

How are you handling user accounts? LDAP, Samba PDC (which is also LDAP), something else?