[MDA III, XDA III, PDA2k, 9090 General] Jiggy:
From what has been said (and not having seen your contract with the Link or the full surrounding circumstances) it sounds like:

1 Either the link is in breach of its contract/its obligations to you as a consumer under Sale of Goods Act (SOGA); or

2 You have an actionable remedy for misrepresentation against the Link shop involved (you would need to verify that there is no small print at the point of sale or alongside the demonstration phone defining exactly what sim free means/that you weren't informed of what this meant by the sales assistant).

Absent any definition of Sim free I think it is reasonable to intrepret this as available for use with any network.

Contract/Sale of Goods Act

There are certain terms implied into all consumer contracts by SOGA. The most important being that the phone is of satisfactory quality and fit for the purpose and as described. Important here is to check through the point of sale posters and leaflets etc (see above). Also when you were speaking to the sales representative did you make know to him or her that you would be making use of this phone with another sim. If you did then this puts you in a real position of strength as you will have expressly made a particular purpose known to the vendor. If not you still probably have a reasonable case that either the phone is not of satisfactory quality (given the manner in which it was described) or that there is an actionable misrepresentation.

Misrepresentation

There are 3 types of misrepresentation (innocent, negligent and fraudulent) with technically differing effects upon your contract. But leaving the legal technicalities aside, at the very least there is a good argument that there has been an innocent or negligent misrepresentation by the Link here aside from a breach of SOGA. Either way you are entitled to demand that the Link resolve this situation to your satisfaction or threaten to take them to the small claims court.

Conclusion

Where you get to, is do you want the phone? If yes, write to them and demand that they resolve this with 02 forthwith. State your legal rights to them as outlined above (remember to think about your particular circumstances). Alternatively if you don't get anywhere say that you will and pay the necessary unlocking charge to O2 and will seek a refund of this charge and your costs from the Link (keeping the Link notified in writing and retaining all paperwork and receipts). You can then take action against the Link (if necessary) to recover it.

If you don't wish to keep the phone, then return it to them and demand a refund immediately. Do not delay.

Finally, there are various helpful guides to your rights as a consumer on the government sites - see dti.gov.uk and look for sale of goods act. Remember that everything depends on the facts of a particular case.

Good luck

P.S Finally, having given some pro bono advice, I would appreciate some help in return from anyone who would be willing to spend 30 minutes on the telephone with me going through the upgrading process. Having read through Wiki I am getting lost with all the Dos commands root files etc. If anyone can, please PM me.

Thanks J