There is an odd quirk when using NFS partitions for mysql data storange under Ubuntu. While there have been several problems with NFS partitions when mounting at boot time through fstab (see here and here for example), this one exists on the current LTS version of Ubuntu and the symptoms are slightly different:
The simple workaround is to add a couple of commands to the /etc/rc.local: first issue an ls and then restart mysql. Unfortunately it looks like the NFS clients are still somewhat buggy in Ubuntu when remounting NFS partitions during boot.