Okay it does sound as if the problem is most likely on your end but your network is not entirely exonerated. Unless your ISP has run ethernet directly to your location (unlikely unless you are in a dormitory or apartment) there will be a DSL modem between your AEBS and where the network enters your premises. That modem could be blocking the uPNP. There is also the possibility your ISP has elected to block uPNP as a security measure to protect Windows users on their network from hacker exploits.
I know you did a lot of troubleshooting but you haven't done this, try creating a new account on your computer. (System Preferences > Accounts and click on the plus sign (+) at the bottom of the list of accounts). Setup the new account to connect with your MobileMe account and see if BTMM works in this new account. If it does work then the problem is isolated to your regular user account on your computer. At least that will narrow the solution space.
