I actually got “Back to My Mac” to work for about 10 minutes last Monday night. It has never worked since. I have an Airport Extreme and everything is configured per Apples instructions. I finally called Apple Support to get more help. Well, Apple phone support does not support dot mac issue and this is a dot mac issue.
The agent asked to go to to this Apple support site where I read the following

Attention Back To My Mac users
In the coming weeks, we will be improving compatibility with home-based routers and various network environments. So if you find that you cannot access your remote Mac right away, please be patient as we work to improve the service.
For instructions and troubleshooting information for Back to My Mac, click here. For more FAQs about Mac OS X 10.5 Leopard and Support contact information, click here.

I guess I’m surprised to find out that you have to fill out a form (see below) to get support for something as hyped as “Back to My Mac.” Well I’ll fill the form out and see what happens. For now there no going back to my mac unless I use Apple Remote Desktop which works wonderfully.