As far ass I know (I am employed at a mobile company :p) this error is only caused by the network, so it will probably pop out no matte what handset you are using...

As jasmin said, changing your sim card might really do the trick... I really don't know witch exactly is your case, but most phone companies give you the option of changing your sim card (usually free, under some conditions) and keep your phone number, additional offers and so on... Try calling customer service, they are sure to tell you more about that...

:) best of luck