Yay, I got my phone unlocked. It took 4 hours and cost me 50 euros though, using some app I got online (From here). Worked pretty well, it was a bit weird. It does the unlock in two stages, first it reads data from the phone, then it sends it to a online server to be put into a queue for processing. Once it's processed, you get sent an e-mail, and you can do phase two - unlocking the phone.

I also phoned O2 customer services to get my old number transferred to the new SIM card and had some silly conversation. First, the guy on the phone needed to know when I last topped up the old SIM, the balance and how I last topped up. Which I very vaguely remember. Then it went like so:
"Ok, can you tell me the serial number of the new SIM please?"
"Err, where would I find that"
"It's on the SIM"
"You mean on the SIM underneath the battery in the phone I'm using to call you?"
"Oh."
Still, it's done now and I should have my old number back in a day or two. Wheeeeeeeee