I had the same problem: backups failed with the log entry "Backup - Unable to connect to the Storage PC." and the console showing that the storage PC was offline even though I knew it was not as I could ping it from the machine where the backup was failing.
This is how I solved it.
First I tried:
1) Re-booting both machines - still the same problem.
2) Running updates - both machines were on the latest level
.. but that didn't work, then I tried....
3) Restarting the LogMeIn services using Control Panel>Administrative Tools>Services and then stopping an starting the 3 listed LogMeInBackup services
Then the storage Pc appeared again on the machine to be backed up.
I guess that it was the restart of the 'LogMeIn Backup Storage PC Service' on the Storage PC that did the trick.