What phone brand and model is your new phone? What phone was your old sim card used in? I believe as long as the phone is unlocked to use any network, and the phone can accept those networks, you will just have to go to your phone operator and request a compatible sim for your phone, stating the sim card type.
What frequencies the phone can accept, and what frequency the phone company you want to use is projecting their network on, are important. 3G covers practically all of the UK now so should be relatively safe with any network using that. I believe for the UK 2G and 3G use 900, 1800 and 2100mhz, although someone might be able to correct me on this if not.
For unlocked foreign phones that do not work even with the correct sim, they may need to be set up to accept the network ie accept the correct frequencies, by entering a hidden menu (often accessed by a set of numbers on the keypad, which can vary according to phone).