That happened with me
(O2 PAYG in the UK)
I put in the WAP setting instead of the mobileweb settings that I used before and it worked, not sure what my speed was on mobileweb but on WAP it is .4Mb/sec