The first time you select the voicemail button your an iPhone, in typical Apple fashion, it offers to help you configure your voicemail. This was much nicer than the traditional voice prompts one normally has to navigate, but the final step (talking to the network) repeatedly failed for me. Google indicated that it might be necessary to manually activate the voicemail by calling 1750, but that did not work for me. O2 customer service suggested that turning the voicemail off then on again would help (1760 [send] then 1750 [send]) but the setup failed again.
The solution that eventually worked for me was to configure voicemail in the “old-fashioned” (“non-visual”?) manner by dialling 901 and then following the tedious voice prompts. Once this had completed, I retried the iPhone visual voicemail setup using the same PIN as I configured at the voice prompts, and it worked first time.