I've found a fix for my 3G connection problem.
I'm with Telstra (Australia).
Two bugs:-
1. They set the APN to telstra.mms - this is of course incorrect, it should be telstra.internet. This wasn't the solution however.

2. They set the Proxy to manual with all its' associated settings.
However I suspect these are not fixed and can vary from time to time.
I set this to Automatic and now have a stable 3G connection.