O2 were probably talking about unlocking the phone... Rather than the PUK code
PUK Code - On the Sim card has nothing to do with the phone itself, this is requested if the sim card has a pin code and someone enters it incorrectly, it will then ask for the PUK code. The PUK code can be obtained for free from the network the sim belongs to... Entering the PUK code wrong too many times will block the sim completely and you will then have to get a new sim card. The easiest method to get the PUK code is usually to ring the network customer services number from another phone, however some have an online option like O2 where you just enter your phone number and it gives you, your PUK.
Unlocking - Unlocking is usually removing a phones sim lock, a sim lock is placed on a phone by the network to stop you using a sim card from another network. The network subsidises the cost of a handset, so you are not really paying the full price of the phone, they expect you to stay with their network. As an example a sim free Nokia phone could be £150, this would mean it would have no network branding and would work with any sim card you like, the same phone could be anything from £90-150 on pay as you/contract etc, however it will be branded by the network and usually locked so you can only use their sim cards. Unlocking removes the locks on the phone, so even though it is a network phone you can still use the phone with other networks. You can unlock most phones, at phone shops or the network will provide the unlock code for you. This is probably what O2 were going to provide for £20. However O2 dont always lock their phones in the first place, so if the T-Mobile sim is now working then the phone wasnt locked
if its now asking for a Restriction Code, or is displaying some other similar message, then it does have to be unlocked
Unblocking - Unblocking is illegal, this is usually changing the IMEI (Serial Number) of a handset that has been previously reported lost or stolen. If you lost it and it legally belongs to you, then you can contact the network and they should turn it back on.