First, you should be able to activate through iTunes. Pushfix 2.0 would add the ability to see what is going on with your push notifications for diagnostic purposes.
If push notifications worked on 3.0.1 with that same plan configured on your phone, then they will work on 3.1.2.
It just isn't working now because you probably don't have a push certificate or are using a shared one.
BTW, MEdia Net is a weird one in that it is WAP, but they also allow many other protocols. Usually when a plan is WAP, it only allows port 80 and 443 for web traffic.
I found info on it here : http://en.wikibooks.org/wiki/AT&T_Mobil ... figuration