We can go through the methods here briefly!
iTunes does NOT change your IMEI - the only way that could have happened is if you updated from 1.0.2 to 1.1.1 with your unlocked phone.
You should be clear!
You can revirginise your iPhone - but it looks complicated although in the long run it MAY be better for you than iPhoneSIMfree.
or you can use iPhoneSIMFree.
You would have to read one of those links about how to restore your iPhone to 1.0.2 and then activate/Jailbreak.
I Personally do NOT LIKE winstaller as it caused my phone to get stuck in restore mode and I had to restore it to get it working!
Assuming you get down to 1.0.2 - iTunes will tell you that you got an error at the end.
THAT IS NORMAL!
Use AppTapp so that the screen will change to the activate screen then do the activation using WINStaller (ONLY for 1.0.2)
WINStaller is a download from the IPSF pages from their userguides to activate.
DO NOT USE WINStaller to jailbreak - use AppTapp its much better and safer.
If your phone goes to the home page and doesn't say activate then you don't need WINstaller - I am not 100% certain if AppTapp activates as well.
YOU ARE NOW BACK IN 1.0.2 and your phone is STILL LOCKED as when you did the 1.1.1 update it relocked your phone!
Then use Installer (which AppTapp puts on the iphone) and install BSD subsytem and community sources.
Put IPSF on your phone (if you go to
www.gizmodo.com and do a seach for iphonesimfree there should be a video showing an iphone being unlocked and unbricked using a direct web download of IPSF TO Installer... you will have to watch the video several times to get the link - as I dont remmeber it! it is a tinyurl.com address)
Make sure you have bought an IPSF licence before you do this using the IMEI on the BACK of your phone.
DO NOT put your SIM in the phone and if you do then take it out before you unlock it.
Click on the red apple logo in IPSF and it will unlock your phone and unbrick it!
Now when you put your new SIM card in it will have the correct IMEI in the iPhone settings as well *you may have to reactivate again - I do not recall!*
Now your phone is WORKING in 1.0.2 and everything should be working - check youtube as well. If youtube doesn't work do a search for PACAY and that will sort it out.
I actually think PACAY activates iPhones and you may not need WINStaller so have a quick look in the forums for PACAY info (do not get confused between PACAY for 1.0.2 and CARNIVAL for 1.1.1).
Personally at this stage I still think going back up to 1.1.1 is a HELL of a lot of trouble.
IF YOU have a MAC you can use Independece for ALL OF THIS stuff - the activation/jailbreaking of 1.0.2 and 1.1.1... but if your on Windows then you have 3 ways to Jailbreak in 1.1.1.
You can use CARNIVAL, iDemocracy or you can use the jailbreakme.com website.
OF course you still have to activate your iphone to use jailbreakme.com although CARNIVAL and iDemocracy will both activate and jailbreak the phone.
When I did it - I did it manually but looking at both those apps I would rather use iDemocracy...
Follow the instructions on either one of those and you SHOULD have a working 1.1.1 iphone.
BUT you MAY have problems - youtube MAY NOT work and those programmes may have errors when they run - its a chance you take.
My personal advice to you is go find someone with a MAC and use Independence.
It works brilliantly and will make everything much easier... no messing around with AppTapp or PACAY/WINstaller - Independence will do it all in 1.0.2 AND IN 1.1.1....!!!!!
You can always add Installer later using Independence as well (although I have had issues with installer and I am not sure Independence patched my springboard correctly).
At the end of the day however my 1.1.1 iPhone works perfectly as normal after using Independence.
-------------------
If what I said gave you a headache and confused you then you know how I feel - Independence makes it all so easy - unfortunately on Windows it is still confusing!