The thing that's even weirder is I installed Ubuntu (and I'm liking it so far) and the internet connection, as well as everything else, works flawlessly.
I think Windows and your wireless utility are both trying to control your wireless. This happened to me once, but I don't remember how it happened. Also, clear your PM's