I had problems setting up my Back to my Mac, but I finally got it working. I have the newest AEBS connected to an ATT 2wire.
A few things you should make sure to do to get it running. Make sure NAT is checked on your Airport Utility under "Internet". Also, log in and out of your .mac, turn on and off you Back to my Mac preference, and make sure File Sharing is turned on. Also, enable Automatic syncing.
What finally made my BMM work for me was to run my Airport under Bridge Mode. Hope that helps.
This is an amazing feature, can't wait to use it more! Between this, Screen Sharing, and Time Machine, it totally makes Leopard worth the price. Btw, I got .mac just for this feature.