Hi, KRO.
I'm in (somewhat) the same situation as you and have come to the conclusion that it is an XP problem. I have two PCs on the desk, one running Windows ME and one with XP on that I use only rarely.
The ME computer behaves in the "normal" way, I switch on the PC, open my browser, enter a URL or a bookmark and the connection box pops up, dials and bobs your uncle. However, with XP, all I get is "the page cannot be displayed" and a load of ramblings about checking my connection. I have checked my settings as per the advice already given, but to no avail. I have got round the problem on the XP machine by copying the connection icon from Network Connections to the Quick Launch bar so that I can easily get connected with one click of the mouse on the icon.
Hope you get it sorted one way or the other.