Gentoo 2004.2 (2.4.26 kernel) server has been running for 9 months now.
Today rebooting a client (same kernel) got "mount: RPC: Timed out" errors

Turns out the server stopped exporting the nfs shares.

Running
/etc/init.d/nfs restart
I get
"Error exporting NFS directories"

Other servers (mail, samba, apache) all work fine; that is, no connectivity problem.
Have not made any changes to the server.
Rebooting the server has not helped.

Interesting to note that after restarting nfs on the server and trying again on the clinet I get

bash-2.05b# mount /mnt/public
mount: server1:/shares/public failed, reason given by server: Permission denied
bash-2.05b# mount /mnt/public
mount: RPC: Timed out

content of /etc/exports

/shares/documents *(rw,sync,all_squash,anonuid=1000,anongid=100)
/shares/public *(rw,sync,all_squash,anonuid=1000,anongid=100)

I noticed that if I remove the contents of
/var/lib/nfs/etab and /var/lib/nfs/rmtab

NFS restart with no problem

after that the fisrt mount from the client (either one) works but the second one times out.
at that point if I try to restart NFS it fails like before


Any idea?

an invliad entry in /etc/exports would be the obvious culprit, but you've not shown us te content of it...