This exact same thing happened to me and I spent hours doing the turn-off turn-on, plug-out plug-in thing.

It turned out there's a little button on the front of my laptop that disables the wireless connection and that I had accidentally hit it while moving the laptop away from Abby (who is insanely jealous over the laptop).

Anyway, I got the same messages asking me to check my wireless connection and apparently it was referring to the button. Once the button was pressed, I was back in business.

Good luck!