I just solved my problem, which was the same perplexing message that kept popping up. It happened to be a Time Machine issue. When I installed Lion, apparently the Time Machine had been turned on by the installer because it kept searching for the Apple.com server, to which I'm not subscribed. Prior to the installation I had always backed up to an external HD; not Apple's online service.
Searching Apple Support Forums, I found "Troubleshooting Time Machine' and followed the instructions to "reset Time Machine". Now things are back to normal. I hope this is of some help.