Enable iPhone Voicemail Divert
After some further googling I have sorted this now. It appears that all UK T-Mobile users get an individual Voicemail divert number. Dialling 222 for the first time should have set this up for me but it didn't.

This worked for me:


I completely reset all divert options by dialing ##004#
I then re-dialled 222 and a message said that number had been set up and I need to reboot the phone. 
I also got an SMS with my voicemail divert number in it.
I rebooted my phone and sent **004*+[the number from my sms]#


My voicemail is now working as expected!