Many Fingers in Many Pies.

If you have problems with Back To My Mac and Orange Livebox

It appears that the Orange Livebox has “buggy” dns. Try putting these two dns address’ in your DNS Servers list in the network settings on your mac 208.67.222.222, 208.67.220.220

Thanks to Apple support discussions (in particular a guy Called Snoop Dogg (no relation I think)) and openDNS, I now have Back to My Mac finally working - no more annoying console messages and a .me service that works fully.