NFS: permission denied. Help?

[Gilboa Davara]

Hello all,

I've got a private network that been running flawlessly for years. (With
minor/major upgrade now and then)
My file server is running CentOS5 (SELinux targeted) and my Workstation
is running FC6. (SELinux disabled)
I'm trying to access a certain NFS share on my workstation (from the
CentOS server) and I'm getting "EACCESS" when I try to mount the share.
(using autofs and manual mount)
A couple of things:
1. The setup has been working perfectly up until two days ago. No idea
what changed.
2. autofs fails silently while manual mount fails on "Permission
denied".
3. /etc/hosts is valid. I can ping from each machine from the other.
4. /etc/hosts.allow/deny are empty.
5. This is not an SELinux problem. (SELinux running on the client),
using wireshark I can detect the error coming from the server.
6. There's nothing in /var/log/messages on both ends. (Only the usual 
"authenticated mount request from blah for blah.)
7. I restarted the nfs, portmap and autofs service. Nada.

Help?

- Gilboa