Well, I was kinda amazed that Apple has built in quite some nice console tools for debugging, so open an terminal and run the following command:

echo "show State:/Network/BackToMyMac" | scutil

The output should already give you a raugh idea about what is going on or what isnt. For this feature to work, you have to enable UPNP in your router by the way, otherwise your Mac won´t be able to automagically forward the ports from your router to your Mac. If you use an Appe Airport or similar as a router you won´t be bugged by this matter, but with other vendors like Linksys, NetGear, AVM, etc. you have to check the manual on how to do that, since te default is usually off.

If you want to dig a bit deeper and you are familias with tcpdump you might want to try the following:

• open two terminals
  (replace 192.168.178.1 with your routers IP address)
  
  

  sudo tcpdump -A -s 0 -i en0 host 192.168.178.1 and not port 53

  dns-sd -X udp 123 456 789

  let that two commands run in a seperate terminal, and kill both after roughly 20 seconds.
• the captured packets should tell you what is going on...