Many folks were excited when Apple announced Back to My Mac as part of MobileMe. Being able to remotely access your Mac from anywhere sounded like magic. We're used to products from Apple that "just work" but for most people most of the time, Back to My Mac "just doesn't."
To maximize your chances, you're supposed to use a supported router, but even that's no guarantee. At home I have an Airport Extreme Base Station (Wireless-N), and at the office I have an Airport Extreme Dual-Band model. I don't think it's possible to get a "more compliant" setup, yet I still can't get it to work most of the time.
Under the adage "nothing ventured, nothing gained," I took a chance and signed up for a free account with DynDNS. DynDNS gives you a free hostname which will go to your computer even when your IP address changes. There are scads of DynDNS domain names available, but for the purposes of this example, let's assume that your domain name is imac.homeip.net.
After you've signed up for your free account and chosen a hostname, download and install the DynDNS Updater for Mac and install it on the machine you want to access via Back to My Mac. (If you want to do this for more than one computer, you will need a different DynDNS hostname for each computer. You can get up to five at no cost.)
Once you have it running, make sure that it has updated, and then switch to your other Mac. You could launch Screen Sharing.app directly from /System/Library/CoreServices, but a much better suggestion is to install the free ScreenSharingMenulet which will sit in your menu bar. ScreenSharingMenulet will remember hosts that you have previously connected to, meaning that you don't have to re-type the hostnames. Click on the menu bar icon, select "New Connection..." and then enter your DynDNS hostname (i.e. imac.homeip.net) and check the "Add to My Computers" box so it will appear in the My Computers sub-menu in the future. Click "Connect" and cross your fingers.
If it still doesn't work, I have a few more suggestions, but I warn you, we're going to get a little technical here. First, you're going to want to setup a DHCP Reservation for the computer you are trying to connect to. The process isn't very difficult. Essentially what you are doing is telling the router to always assign the same IP address to the computer you are trying to access. After you have done that, tell the router to send all traffic directly to that computer. On the Airport Express this is called the "Default Host" and is found on the Internet Tab under "NAT" but other routers have different names for it (I believe Linksys routers refer to this as the "DMZ" host. Check your router's documentation if you're not sure.)
Warning: once you do this you are bypassing your router's firewall. Mac OS X has a firewall, but it is not enabled by default. Launch System Preferences and click on the Security panel followed by Firewall tab. If it doesn't say "Firewall: On" be sure to enable it.
Update #1: Several comments below suggest that putting your Mac as the "Default Host" or "DMZ" will make your Mac insecure. I don't know of any evidence that that is true - "gut instinct" is not evidence - assuming the Mac OS X Firewall is enabled. That said, you can try using Port Mapping or Port Forwarding to forward to port 5900 (the port Screen Sharing uses). If you can block all access to your Mac except for that one port, it obviously reduces the number of potential ports that a malicious attacker could try to access your Mac. As one commenter suggested, you could even map different ports to forward to port 5900 on various Macs behind the same DynDNS hostname. In AirPort Utility you can find Port Mapping configuration under "Internet" and then click on the "NAT" tab. This will still require that you use DHCP Reservations, as above.
If all else fails, you might want to try another direction: Back to My Mac through iChat. I haven't actually tried that, but it's another option.
I can't explain why using a DynDNS domain name works more reliably than the built-in Bonjour sharing/connecting method, but after days of unsuccessfully trying to connect to my work computer, I have been able to connect via DynDNS without fail. As my Dad taught me long ago, "A good strategy is that which works."
Update #2: I have been using this setup for the past week (using Port Mapping for port 5900, not the DMZ), and have had a 100% success rate connecting BackToMyMac using my DynDNS. This is a dramatic improvement over trying to connect via the Finder.