Why doesn't my SIM card does allow a connection to this network?
It appears several sites suggest preventing the phone from using 3G. I have gone into Settings -> Wireless &amp; network -> Mobile networks -> Network Mode -> GSM only.

This appears to have fixed the issue for me. Of course this wouldn't be a solution for anybody who relies on mobile data (but my provider charges so much for data that I'm wi-fi only).