I'm unsure how the "DNS check" tool could not work in this case; I believe it is as simple as determining if DNS requests get sent to the IP's that are now controlled by the FBI. This would cover maliciously changed DNS settings in both the router (via changing DNS settings from the typical default of DHCP acquired) and the machine itself (via the hosts file).
Routers cannot be 'infected' per se (well, they can, by forcing a malicious firmware to them, but since that differs between models and is rather involved it's not really as economic from the malicious authors point of view as just fiddling with the settings. Also, in that case a reset wouldn't resolve the problem either, since it just wipes the settings memory, and the malicious code would remain. so thank goodness for that. One could argue that maliciously intentioned settings are as much an infection as maliciously intentioned executable code, but malicious settings can never do nearly as much damage as malicous code, since it's still confined to the capabilities of the program that uses those settings. Those settings can open holes to new infections, of course, and are certainly (as in this case) dangerous. In this case, the computer gets infected, the malware changes the hosts file and/or manages to push changes to the router, and goes on. The infection itself is only the executable trojan horse; remove that, and the infection is essentially gone. However, what is left are the various settings that were changed. In this case, those changes are definitely malicious, but calling it "malicious code" is somewhat misleading. They do have an effect, but my understanding is that malware 'treatment', much like medical treatment, aims to deal with the causes and not the symptoms.
I don't know the technical information about DNS changer and how precisely it works particularly with regard to routers, but it's reasonable to assume it only works on a subset of routers, likely chosen to maximize the ability of the trojan to change settings by targeting popular routers. Each one would need to be dealt with "specially" by the trojan, since each one has a different web interface, so it needs to know the sequence of http requests to send to the device in order to change the DNS settings.
Geek9pm: No router has the web-administration feature enabled by default, and I would hope people that do enable it have changed the password and username from the default!
I believe google and facebook warn users whose DNS is redirected as well, though I cannot find any confirmation on that. If so, I would imagine most of the less tech savvy use at least one of those sites, which means that they have essentially ignored warnings telling them what is going to happen anyway.