I fixed it.
It turns out it was a DNS issue all along, although I don't know how as I was able to ping psgw.t-mobilesgws.com from the phone and do manual DNS lookups from the phone.
I did a DNS lookup for psgw.t-mobilesgws.com on my laptop and got the following warning before the IP addresses:
Truncated, retrying in TCP mode.
So I'm guessing the the blackberry will only use UDP (the default) for DNS queries?
So I took one of the IP's (220.127.116.11) and typed it into my router so that it would respond to DNS queries with that IP address and not do a DNS query of its own. But why wouldn't the router return "looked up" IP's via UDP? Or why would the blackberry reject such IP's?
Anyway I reconnected my blackberry and it worked flawlessly.
I even called my wife to tell her I had it working.