There are a couple of threads here that deal with this, although none actually provides any substantive answer as to what exactly is going on. It appears to be a SNAFU and, disappointingly, the Adobe folks have not found a solution since at least June. For what it's worth, here's how I have dealt with the problem (MAC user):
"This could easily fall into the "not germane" category, but I was having a very similar problem. LR periodically fails to synch, telling me that suddenly I am not connected to the internet. I do/do have LR on the allowed list on NORTON Firewall, and indeed the synch does usually work. However, I found that when LR has this outbreak and spontaneously decides that I have no internet connection, I shut off the Firewall completely and this allows LR to re-establish the connection and execute the synch. I'm not terribly IT minded, but it's as if there is a separate 'routine' or 'program' embedded in LR to execute the synch that the Firewall doesn't like, even though I cannot actually see the outgoing connection on the Firewall log."
I found out it was my computer. For some reason it (slowly) started having issues with the internet. First it was certain apps like Dreamweaver, then nothing could connect to the net. Everything (save for browsers, email and updates) worked though. I had to buy another computer. Thanks for your help though Federico Alessio.