Are you pressing save when the setting's come through ? and then making that profile activated in your message setting ?
Whenever I have a new phone I just go here
http://www.o2.co.uk/services/ota4/input2 then select phone make, model and tariff. then just enter your mobile number and hit send.
When settings come through normally just click save. If not asked to make default profile go into your message setting's and set the O2 profile to the one is use.
Also would still be classed as Payandgo.