I was having the same problem but found a solution that worked for me.
1. From the iCloud System Preferences pane, uncheck the Back to My Mac checkbox to turn it off.
2. Open the Keychain Access app (in Applications/Utilities).
3. Click the "System" keychain (You'll see keychains near the upper left of the app window).
4. Make sure "All Items" is selected in the "Category" box below.
5. In the results showing to the right, look for any key whose "Kind" is "Back to My Mac key."
6. Delete the key(s), authenticating with your password to do so.
7. Back in the iCloud System Preferences pane, re-check the Back to My Mac box.
At this point, Back to My Mac started and the "server not responding" message did not appear.
I'd tried unchecking and re-checking several times before to no avail. I hope it works for everyone.
Maybe the keys we had were tied to MobileMe and became invalid when MobileMe shut down?