I have nearly the same problem. Same router (although I've also had a D-link DI-514 with the same results), multiple XP boxes and (in my case two) Fedora Core 3 linux boxes. By making sure Samba is set up with my workgroup name and runs at startup, my windoze boxes
can resolve the linux boxes, but the reverse is not true. The linux boxes can ping any address on the network (internal or external) by IP, but they can only resolve external (internet/WAN) addresses by name.
It appears to me that I get the windoze boxes to see resolve the linux machines by mimicking standard Win32 behavior through samba. However, that is only true in regards to the linux box "broadcasting" its information somehow to the windoze machines (WINS, perhaps?). However, nothing seems to be able to make the linux machine use whatever windoze does to resolve internal names.
As I understand it the router does not act as an internal DNS server -- only as a passthrough DNS server for WAN addresses. I dunno... I'm getting fairly frustrated with trying to make it work...
-eagle79-