Hmmm, well basically the same setup i'm using.
How is your media center connected to your NAS? (UTP or Wireless? , Speed?, switches?) If you were to copy down a large file (1 GB +), what transfer speed are you getting?
Have you tried copying some files down to your MC HD to see if its still locking up when playback is local?