Why am I being told I'm not connected?

I'm having this strange problem that perhaps someone can help me with. I've just recently done a wipe and re-install of XP.
Everything seems to be working fine with one exception.
When I use the search icon at the top of the browser window(the little magnifying glass), I get the search window at the left of the screen as normal. I enter my search like I've done a million times before. Now, though, when I hit the search button, I get a statement in the search window that says....."Unable to connect. The Web site is currently unavailable or the connection to the internet has been lost. Make sure you are connected to the internet and try again."
What gives here? I'm obviously on-line...I'm here writing this aren't I? I have complete access to the internet and can go where ever I want. So why can't I complete a search?
Anyone wann try their hand at this one?
Anyone?
Someone?
Please.
Thanks.