"Back to my Mac isn't working properly because your DNS server isn't responding. Contact your ISP for an alternate DNS server address, and enter it in Network Preferences".

I did what you suggested but I'm still getting the message saying Back to My Mac isn't working. Are you saying I'll still get that message but it is working? My cloud is maxed out and I want to take things off and back them up to my computer.

I think you need to contact your ISP as the message says, only they will be able to provide you with their alternate addresses.

Same issue here.

Had it previously setup and working perfectly, but now it gives this error. Very strange.

I think this may have something todo with upgrading to Mavericks?

I have the same problem and my ISP says their DNS servers are not blocked in any way either. We tried my ISP DNS servers and we also tried Google DNS servers. I called Apple and they said they don't handle these types of issues. I did not have this issue before I upgraded to Mavericks and it immediately happened after I upgraded. I'm very unimpressed with Apple's assistance.

Ha yes. I called apple care support and they had me clear my user preferences. Restarted my computer and then it wouldn't restart. Awesome. Had to restore the entire thing from a time machine backup. Support is worthless.

Same problem over here. "Back to My Mac" indicates that it does not work properly because DNS server is not responding.

I have a Time Capsule network running DHCP and Nat behind an ISP router.

Everything seems to work perfectly from a network perspective except this annoying message. I tried to enter all DNS possible entries (10.0.1.1 that's TC, 192.168.1.1 that's the ISP router, 82.x.x.x that's public DNS for the ISP) in the Network preferences without any success.

I came to think it has something to do with Mavericks update.

I am also having issues with BTMM since moving to Mavericks.

In System Preferences > iCloud > BTMM it has thrown a series of errors, stating issues with DNS, UPNP, and other router settings. I am using a Netgear WNR2000v4 with the computer to be accessed. I have also tried it with a airport express, and I'm getting similar errors. I'd love to know when this gets fixed, so that I can use the network file sharing feature, which is much more straight forward than LogMeIn's offering. Get to work, Apple ppl!

I have have the same basic setup as you. Tried the same. Only started with Mavericks. One thing about my situation is I can access my iMac w/Mavericks at work consistently. It's only accessing my MacBook Air from my iMac at work that doesn't work.

Same issue here. Airport Extreme and receiving the error. Didn't start until Mavericks.

Same issue here ... and i find it weird that apple is not considering the issue ... I have bought this "airport time capsule" because of the internal storage and read that is accessible from outside your local network ... now i feel disappointed I could've get the linksys in less than the price i paid for it and it have the utility app to remotely login to it without all this hustle ... I believe apple should reconsider this and make a utility for remotely access the wirless device and internal storage without all this .....

I am having the same problem too. Macbook Air running Mavericks, Mac Mini runing Lion.

I can access the Macbook from the mini, but I can't access the Mini from the Macbook whilst out of the house.

No one seems to have a solution for this which is very frustrating!

I hate to be a "me too" but– me too! The strange thing is that about a week ago BTMM was working intermittently. Now none of my computers that should show up under "Shared" in the sidebar appear. I've been using OpenDns as my DNS server address.

Same problem here.... I have a Mac Mini Late 2011 at home and use a Mac Book Air Mid 2012 at the office, both running Mavericks 10.9.2. Never used BTMM before, but it works fine when both macs are in the same network at home, but i'm having this DNS issue message when trying to connect from office. Actually, at a randon moment my Mac mini showed up in the Shared section in Finder today and I was able to connect and shared my home screen. After closing the lid and openning again the connection was lost and the icon was gone from 'shared' section. Never showed up again...

I already tried to set openDNS and Google IPs in wireless settings without success.

Pls any help is welcome.

New to BTMM, I got stung today with the silly DNS problem message. Solution:

1) Flush DNS cache with:

dscacheutil -flushcache;sudo killall -HUP mDNSResponder

2)System preferences > iCloud > untick BTMM then tick it again. The warning should have disappeared.

Edit #1

Apologies for the noise. The warning has come back 😟

Edit #2

Just found out that BTMM is not compatible with double NAT. That's not helpful.

http://support.apple.com/kb/TS1208