Hey Fella,
I had the same problem when I fired up my iphone, you need to turn on the 901 message service with o2 by dialling 1750 from your phone, this will activate the voicemail and bingo you are in business.
Its smart system once working - shame they cant tell you how to switch on you just gotta guess your way through!!
Hope that works.
C.😎