From ModMyiFone - Wiki
Credit goes to the hackint0sh guys for finding this out.
For those who've unlocked and have a non-functioning Voicemail button, here's how to fix it:
1. First, take note of what your voicemail number is with your current provider (for example, in Spain the Vodafone voicemail number is 177).
2. Click the phone button in your iPhone.
3. Click the keypad tab.
4. Type the following code:
*5005*86*xxx#
Where xxx is your voicemail number, using the Spain Vodafone example, you would be typing *5005*86*177#
5. Hit call.
6. Give it a bit, and the code will be set.
7. Hit the voicemail button, and it will now call your voicemail.
n.b.: So far, some voicemail numbers starting with "*" or "#" work by replacing the * or # with "+" (use +611 instead of *611) this works with some carriers, but not with others.
