[Solved, Can be Closed - Please see Second Post]
The gaps in playback vary but have been up to 12 seconds.
I haven't noticed it on any other types of files.
There's nothing too exotic about my set-up, except perhaps using Powerline plugs to create the wired connections from the Pi to the router, and the NFS server to the router. They're rated at 500Mbps.
I've also the Wolfson DAC.
I'm absolutely loving the system otherwise, the sound is gorgeous
Debug info: http://pastebin.com/gitbRjAn