NST (
http://networksecuritytoolkit.org) is based on Fedora, but is one I've used before. Nice GUI.
The thing is, if you can resolve domain names with a live CD it's just one more confirmation that something in windows is screwed up. :-|
I think we're all rapidly moving towards that assessment, anyway.
Back on the 'cover the basics' front, you swapped ports on the router with another machine to ensure the problem didn't move?
Then you swapped NIC-card-end of the cables with another computer to eliminate the cable from the equation?
Did you try uninstalling the NIC from Device Manager then reinstalling it using the latest drivers?
Besides fixing any possible problems with driver corruption (or mixing, if it's been upgraded numerous times), that should redo all the bindings, too.