I would start by making sure that the settings are the same on every computer (have to rule it out)... then on each machine, right click on the network interface settings and do properties, double click on IPv4, then advanced.
From here, I would click on the DNS tab and manualy add the server in the top list then select the option "Append these DNS suffixes (in order):" and choose something such as .local or .mynetwork then tick the bottom two options.
Restart all machines after making these changes and go to the command prompt and type ipconfig /renew
followed by ipconfig /registerdns
Next, at the command prompt, type "Nslookup" and just try the name of one or two machines and see what happens.
If you are still getting no where, check DNS settings on the router, it sounds like it is not allowing other machines to register / is a caching DNS server for the internet ONLY, if it does work - cool.
If this doesn't help, you may be best off just using hosts files or using a different firmware - but, hopefully it has helped.
Edit - Also, Just thought - Remember to check that ICMP Echo is allowed on the Windows Firewall!
Best Answer
As far as the DNS is concerned, it really doesn't matter. Your router will end up doing the lookup to your ISP anyway. As for performance, you will likely get better performance using your ISP directly since your router is pretty under-powered and will be relatively slow in responding to queries. However, in theory, if your router is able to cache queries, if you visit the same domains repeatedly its possible the router will be faster.
You can use a DNS Benchmark Utility to test both options and decide for yourself.