i'm totally jealous, i'm from manchester i've read your other posts and i read you were there for 8.15, i've been everywhere, i cant find one at all, i'm gutted!
every o2 shop i speak to says there getting some in on tuesday, i'll just have to wait and see!
right lets talk about voicemail, obviously not to insult your intelligence but you've been into your setting and what not and changed your voicemail password, set-up your call forwarding(if required) and call waiting!
then into your phone set up your greeting via the custom way and that should be it!
if not then i'm not quite sure, but no doubt a quick call to o2 and they could possibly do something to help you!
let me know