I don't think this issue has anything to do with the operating system. If Windows users post here, let them post and any solution they have may be worth trying if it isn't OS specfic, which I doubt any solution will be. I say that because I had this error message running Windows Vista Home Premium but Santa was good to me and I just received a new, and my first, Macbook. I thought, surely, this error message is resolved now, there had to be a problem with Windows. Nope. I still have the error message with iPhone and iPad. This error message, in my belief, is originating either from our respective home networks (I'm also using a Linksys E3000 with Tomato FW) or settings within the iPhone/iPod/iPad.
For the record:
iPhone 4 16 GB (six-digit passcode)
iPad 1 64 GB (no passcode)
Linksys E3000 with Tomato Firmware bridged through Linksys WRT54G with DD-WRT firmware, I received this error message before I installed the bridge, not related to the issue.
Any help or ideas or suggestions are welcome, even from Windows users.