Yeah, I know that annoying little message! It used to show up whenever I wasn't connected with my dial-up connection. But now I have't seen it since I got a cable connection. That's how I know it's the connection!
I don't know why you get this message if you are already on the net, but I know it's showing up because it can't find a connection to the net!

-Emo