After getting rather frustrated trolling the various phone web sites my girlfriend suggested I call T-Mobile tech support. I was reluctant but tried. After lots of time on hold and getting them to call me back I eventually reached the lofty Tier 3 support.
I explained my issue, trying to dial out using OS X with an E61 on the Blackberry plan. I joked that at least I wasn't trying linux, the tech said that might be easier.
Needless to say, tier 3 wasn't able to help me.
My girlfriend was impressed that I could stump tier 3.
My ideas to solve this problem was to either go back to t-zones, switch to t-mobile internet, or write a proxy server that runs on the phone. Pity OS X doesn't support personal area network.