Changed carriers - can't access voicemail

My voicemail button no longer works after changing carriers. The new carrier has a different voicemail number to the old one, so I suspect I somehow need to change the voicemail number dialled. Can someone tell me how to do this? I've tried restoring the iPhone and resetting the network settings without success.