Ultrasn0w can be installed on IOS 6 and 6.0.1, you install a fixer from another repo before ultrasn0w itself. However ultrasn0w only supports 1 baseband for the iPhone 4 which was one of the very first ones in IOS 4. So because these guys have updated to anything Higher that IOS 4.1 I think it's was, iTunes as most of us now updates the baseband. Unless they preserved it which is very unlikely.
I had the same problem with a friends iPhone 4. You either buy a sim thingy like Laelipoo said which can easily damage your phone when you put them in, plus there are loads of fake copies out there that give you band reception. It's just not worth it for the cheap money they are. You have to buy a factory imei unlock if the phone is still in contract and its not in your name. If its out of contract the contact the phones network that's its locked to as that is the cheapest way around it as iemi locks can cost from ?40 up to ?110 which is what I have just paid for my 4s.
Here is the best place I have found for iemi unlocking. This is where I got my 4s unlocked from t-mobile and because it still had a year left to go on contract in the old sellers name. The only way for me was to pay ?110.
Check the pricing section:
Unlock iPhone, Official iPhone Unlock, Apple iTunes Unlock
I've done tonnes of research and the best way is to try the network first as they will be the cheapest. If they won't do it, then the site above is the best reviewed and the most reliable site there is I've found.
Good luck and sorry to put a downer on your day.