I am having this problem too. I just upgraded to 10.9, and on my iMac and MacBook Pro, Back to My Mac starts up fine. However, it doesn't start up on my Mac Mini. They are all connected to my local network using an AirPort Extreme Base Station (with Back to My Mac set up with my iCloud account and password and green dot present). The iMac and Mac Mini are connected via Ethernet and the MacBook Pro via WiFi.
On my Mac Mini I've tried all the usual stuff. Turning off, waiting a minute, and turning back on. BTMM still says "iCloud server not responding." I've also deleted all the Back to My Mac keys in my System keychain using Keychain Access and trying again, but that didn't help either.
Here's what's showing up in my Mac Mini's System Log. First when I turn off Back to My Mac in the iCloud Preference Pane:
Oct 25 12:28:31 Mac-Mini.local com.apple.preferences.icloud.remoteservice[450]: INFO: FMM: isLocationServicesCapable: YES
Oct 25 12:28:31 Mac-Mini.local com.apple.preferences.icloud.remoteservice[450]: INFO: FMM: areLocationServicesEnabled: YES
Oct 25 12:28:31 Mac-Mini.local com.apple.preferences.icloud.remoteservice[450]: INFO: FMM: isLocationServicesCapable: YES
Oct 25 12:28:31 Mac-Mini.local com.apple.preferences.icloud.remoteservice[450]: INFO: FMM: areLocationServicesEnabled: YES
Oct 25 12:28:32 Mac-Mini kernel[0]: flow_divert_kctl_disconnect (0): disconnecting group 1
Oct 25 12:28:32 Mac-Mini.local configd[23]: network changed: v4(en0:10.0.1.204, en1) v6(en0:2002:62c5:c1f::3615:9eff:fe18:df54, en1) DNS* Proxy SMB
Oct 25 12:28:32 Mac-Mini.local awacsd[713]: InnerStore GetWakeInfoForZone: no info for 123072138.members.btmm.icloud.com.
Oct 25 12:28:32 Mac-Mini kernel[0]: flow_divert_kctl_disconnect (0): disconnecting group 1
Oct 25 12:28:32 Mac-Mini.local mDNSResponder[45]: Removing registration domain 123072138.members.btmm.icloud.com.
Oct 25 12:28:47 Mac-Mini.local awacsd[713]: Exiting
Oct 25 12:29:09 Mac-Mini kernel[0]: process 729 set trusted
Next here's what's happening when I click Back to My Mac a minute later to turn it back on:
Oct 25 12:30:07 Mac-Mini.local com.apple.preferences.icloud.remoteservice[450]: nsc_smb XPC: handle_event error : < Connection invalid >
Oct 25 12:30:07 Mac-Mini.local com.apple.preferences.icloud.remoteservice[450]: INFO: FMM: isLocationServicesCapable: YES
Oct 25 12:30:07 Mac-Mini.local com.apple.preferences.icloud.remoteservice[450]: INFO: FMM: areLocationServicesEnabled: YES
Oct 25 12:30:07 Mac-Mini.local com.apple.preferences.icloud.remoteservice[450]: INFO: FMM: isLocationServicesCapable: YES
Oct 25 12:30:07 Mac-Mini.local com.apple.preferences.icloud.remoteservice[450]: INFO: FMM: areLocationServicesEnabled: YES
Oct 25 12:30:08 Mac-Mini kernel[0]: flow_divert_kctl_disconnect (0): disconnecting group 1
Oct 25 12:30:08 --- last message repeated 1 time ---
Oct 25 12:30:08 Mac-Mini.local com.apple.preferences.icloud.remoteservice[450]: nsc_smb XPC: handle_event error : < Connection invalid >
Oct 25 12:30:08 Mac-Mini.local configd[23]: network changed: v4(en0:10.0.1.204, en1) v6(en0:2002:62c5:c1f::3615:9eff:fe18:df54, en1) DNS* Proxy SMB
Oct 25 12:30:08 Mac-Mini.local mDNSResponder[45]: Adding registration domain 123072138.members.btmm.icloud.com.
Oct 25 12:30:08 Mac-Mini.local awacsd[737]: Starting awacsd connectivity_executables-97 (Aug 24 2013 23:49:23)
Oct 25 12:30:08 Mac-Mini.local awacsd[737]: Configuring lazy AWACS client: 123072138.p03.members.btmm.icloud.com.
Oct 25 12:30:09 Mac-Mini.local awacsd[737]: Failed to create UTunnel object!
Oct 25 12:30:09 Mac-Mini kernel[0]: flow_divert_kctl_disconnect (0): disconnecting group 1
Oct 25 12:30:09 Mac-Mini kernel[0]: revoking trust for process 729
Oct 25 12:30:09 Mac-Mini.local awacsd[737]: Failed to create UTunnel object!
Oct 25 12:30:09 Mac-Mini kernel[0]: flow_divert_kctl_disconnect (0): disconnecting group 1
Oct 25 12:30:10 Mac-Mini.local com.apple.preferences.icloud.remoteservice[450]: nsc_smb XPC: handle_event error : < Connection invalid >
Oct 25 12:30:52 --- last message repeated 1 time ---
I don't know the meaning of the first and last line which are the same and looks to be significant, or why Back to My Mac turns on on my other two Macs but not this one. I don't know if there could be a firewall problem, but I've got the same firewall settings turned on in all three Macs: the firewall is on and the "Automatically allow signed software to receive incoming connections" option is checked. Could there be iPv4 or iPv6 issues here? (I can get to ipv6.google.com just fine in Safari, so iPv6 in my AEBS seems to be working OK.) Any help or further information would be greatly appreciated. I'm stumped and frustrated right now.