In Android 2.2 from a HTC Desire Z I am frequently finding my phone disconnected from my mobile provider.

When I select my provider from the Settings -> Wireless & networks -> Mobile networks -> Network operators -> Search networks -> <My Provider> I get the message "Your SIM card does not allow a connection to this network".

The only fix I can find is to restart my phone. Problem appears to widely affect Android phones.