A smart bloke here in Australia on the whirlpool forums has found a fix to this problem that worked for me (I'm on the 3/vodafail network). Here is his solution:
To solve this problem, just go to "Setting"->"APN" and untick "Automatic APN", wait a few seconds, then tick "Automatic APN" again...