Well... now it's working. Very puzzling as I'm not convinced I nor O2 really did anything!
For the record, I was talking to O2 first line support for 30 mins and the end result was that they reinstalled the latest firmware remotely on to my router - i.e. the same version I already had. Tried reconnecting and it still hung at "Verifying username and password". Then I had to leave the house for 30 mins (gf forgot her wallet!) and when I got back I was investigating
this thread, where I had similar issues and resolved these by rolling back the firmware. Anyway, before I did that I just tried reconnecting again and the
only thing I changed was in the IPv4 Network settings where I changed my DNS Suffix from "MYCOMPANY.local" to "MYCOMPANY" and it reconnected first time.
So... great that I'm reconnected, but sorry as this probably won't help anyone else! Maybe it's worth getting O2 to redo your firmware and waiting a while, but apart from that.... not sure!