JEsTer's iPhone Information

If you want to get voicemail working on your phone, you will need to enter the following in the phone keypad application:

*5005*86*XXXXX#

Replace the word 'XXXXX' with the number of your voicemail. With vodafone in the UK, dial 121, so it would look like:

*5005*86*121#

Then just press the call button.
Thanks eastyboy for pointing me to this fix.