Voice mail doesn't work after upgrading unlocked iPhone

Yesterday I upgraded my unlocked iPhone from version 2.2 to 2.2.1.
After the upgrade, the Voice Mail my Voice Mail configuration was reset - i.e. it didn't work anymore.

So just for reference - here is the guide on how to set the Voice Mail number on the iPhone (at least this work on a Danish iPhone, originally bought from Telia):

If your Voice Mail number is (+1) 123-1234, you should go to the Phone app, open up the dial tab, and type in the following:
*5005*86*+11231234#

Just for clarification, the template is:
*5005*86*[VOICE MAIL NUMBER INCL. +LANGUAGE CODE]#

And then press the Dial button. That's it! You'll probably have to do this after each upgrade.

Please comment if the template looks different for your country/original service provider!