Sounds like you are using your phone as a dial-up modem, dialling your ISP.
This uses the basic GSM data rate of 9.6k (which is also used for WAP, I believe). Some carriers e.g. Orange support higher speeds (28k?). There are also hacks (involving special init strings) which grab more GSM time slots and increase the data rate, but you pay for it and I don't know if it still works (it used to a few years back).
What you need is GPRS or 3G. The latter has lousy coverage but I find GPRS works everywhere so far (Europe & USA) where there is GSM. Not necessarily on the network which the phone immediately prefers to connect to, but I have not yet not had a GPRS connection. GPRS runs at about 25k; double that in the USA (on Voda, anyway). 3G runs at about 10x that - if you can get it. Most 3G phones (or PCMCIA cards) will fall back to GPRS automatically.
With GPRS, there is no number to dial as such; it is always something like *99# and you don't dial an ISP; the network is the ISP. This means some TCP/IP ports can be blocked, and your SMTP server name needs to be reconfigured (if you are using the ISP's one). Same for Usenet.
I have sent you a PM.