It could be either a phone or a provider problem, so Tesco should have gone through their side to make sure.
As you can't save your voicemail greeting, it seems that its actually a problem on the carrier side than phone.
On the phone, there's two means of activating the voicemail. From your post it sounds like you've tried the first anyway, but they're:
Settings -> General -> Reset on iPhone, and tap Reset Network Settings. The iPhone will reboot.
Alternatively, go to Settings -> General -> Network -> Cellular Data Network, and set the APN for Visual Voicemail to acds.voicemail.
I still think the problem sounds like it's with the carrier, especially as you have trouble setting a greeting message. They may need to reset your voicemail at their end and then you another reset of the settings on your phone.