STAY WITH O2, FOR THE LOVE OF GOD!
I have two o2 phones. When the time came to upgrade/renew one of them, I was going to cancel and move to Orange. I told them this, and they upgraded me from 200 minutes and 100 texts (for £25) to 500 minutes and 300 texts, for £15 a month!
This meant the other phone was now surplus to requirements, so I called up to cancel. They offered me 100 minutes and texts a month for NOTHING. Absolutely free.
Phone companies will do almost anything to keep you as a customer, even if it's give you free things.
Whatever you do, stay away from Vodafone.