Tom--Not sure if it's the same issue, but I have been having DNS lookup issues (also in NoVA.) I get 5-10-second "Looking up [site]" messages, and frequent timeouts, approx message: "Can't find server, check your spelling."
This seems to happen with all browsers, but even happens with my e-mail client (T-Bird) connecting to the cox pop and smtp servers!
I do NOT have data transfer speed problems: just initial connections.
This problem sometimes seems to go away for a while, but only for a short time.
Cox support "cleared a cache" for me (not customer accessible, apparently) a couple of times, and that seemed to help, but again just for a short while.
I had a Cox tech out last week checking the physical connections and signal strength, which he said were all OK.
Most recently, I tried a traceroute (function built into my Motorola Internet modem/gateway) and was surprised that most tests failed after 10-15 hops. That seems bad to me, but I am not a network engineer so maybe it's not significant.
You can see my most recent posting here if you search for a "DNS" tag in the Internet Forum.
Good luck!
Martin