Customers from Manchester, Leicester, Bristol, Birmingham, Sheffield, Leeds, London, Belfast, Kent, Scotland, Wales, and many other areas said they were unable to use their phones for several hours.
O2's "live status checker" website issues with phone masts were blamed for problems in a number of cases.
A search for the Leeds area, for example, said: "Sorry we're currently working on a phone mast in this area. Your service might come and go until we've finished."
A spokesman for O2 said: "We are aware of isolated instances across the UK where some O2 customers are currently experiencing intermittent service. We are investigating the situation and will update as soon as possible."
The spokesman later added: "Further to our previous message where some O2 customers were experiencing intermittent network service, we have taken steps to minimise the impact and some customers have seen their service return. We apologise for any inconvenience and continue to do all we can to restore service for customers who remain impacted."