Many cell phones have downgraded Bluetooth so you can't pair them with other devices.
Have you verified that the bluetooth connection has a dialup profile, and that it is connected sucessfully?
One the dial up profile is connected, make sure the connection settings are correct, see this link for the settings:
http://www.aximsite.com/boards/showthread.php?t=82337
The GPRS/EDGE/UMTS connection has no differences, and the phone will automatically connect to whichever service is available transparently. You need to do nothing special for that.