I rarely reboot my main machine but when I do the export stage for nfs shares took an intoleranly long time. Googling indicated I should install portmap. It was already installed so I tried reinstalling. Still the same problem when I tried
sudo /etc/init.d/nfs-kernel-server restart
The solution turned out to be quite simple. Rather than needing to configure reverse lookup on the the DNS Server I have running (bind9), I simply added the NFS clients to my local /etc/hosts file.
The time to export is not about half a second as opposed to a minute.