I am having the exact same problem with my new DIR-655 on a DNS-323. I just installed the DIR655 in place of a buffalo wireless router that was working fine. My PS3 can see the NAS (although not consistently) but my XBOX does not see it (nor any media sharing pc's i have, which the ps3 can see as well).
I have restored factory settings on both the router and the NAS (doing so re-enabled ps3 NAS visibility), check uPnP, disabled the firewall on the router, but i cannot get the Xbox to see any media servers. I have also tried using static ip's as well as changing the LAN speed from 1000 to 100 with no result. PC's that used to be able to see the NAS in windows media player no longer see it as well.
Any suggestions? Thanks in advance.