T-Mobile voicemail problem with S710

[Guest blahmartinblah]

I have a problem with my V1415 (Vodafone version of Vox/S710) being used on T-Mobile Relax 35.

Dial 121 (hold the 1 button), says:

Your voicemail access number has now been sent to your phone. Please now switch your phone of, and then on again.

The phone receives a text message a minute later, which says:

Sender: Pers

Network message, please delete!

I then switch the phone off, and on, try voicemail again, and get the exact same message. What is the problem here? Can I manually add a voicemail access number? (thought I was meant to dial 121 anyway! Why do I need an access number?!)

Martin.