I also don't want to stream from the PC when I've got a NAS (in my case a WD MBWE) - mainly down to the fact that the XBox and PC share the same monitor.
Didn't have much of a problem streaming from the MBWE - but you need your NAS to be acting as a media server (DLNA?). If you want to check whether its the files that your using that are the problem you could also bung a couple on a flash drive and plug that in. I certainly remember being able to stream iPod-compatible MP4's to the XBox, (
although I'll give that a check after the dashboard update).
You could always post a question on the forums here - there's usually someone with the same setup as you that can help.