I had the same issue connecting to O2 GPRS using a Nokia 6310i. I solved it with help from my service provider and the fault lie with the phones settings!
I had to get the latest WAP GPRS settings for my phone from the O2 website. In addition I had to set the Phone to: -
SETTINGS - GPRS Modem settings - Edit active access point - Alias for access point - Rename TO mobileweb
SETTINGS - GPRS Modem settings - Edit active access point - GPRS access point - EDIT TO mobile.o2.co.uk
But the above only works for O2, you'll have to confirm details with your own service provider.
They also asked me to check my firmware version on the phone by typing *#0000# it should be 5.50 or above (for Nokia 6310).