After thinking I would have to go to an Apple store and invent some story that “a friend” messed up with my iPhone and it does not work any – I want a new one – I was able to unlock the iPhone for any carrier!
It is a “painful” process but with the help of some sites and UNIX knowledge it is done.

1. To start off with, make sure your iPhone is updated by iTunes (check for updates).
2. Then you have to “unshackle” the iPhone. I used iFuntastic. Get it here.
3. Got through the unshackle process.
4. On the iPhone, run the Installer app that should appear on your home screen and install the following three applications, in this order:
   1. Community Sources
   2. BSD Subsystem (might take some minutes)
   3. OpenSSH
   4. Term vt-100
5. Back on your computer download the following files to your computer – open the downloaded folder.
6. Using iFuntastic’s File Manager, navigate to the /usr/bin/ directory and copy the following files to that directory:
   1. iUnlock
   2. ICE03.14.08_G.fls
   3. nor
   4. minicom
   5. bbupdater
7. Navigate back to the /usr/ directory and now create a new folder called local. Within the local folder, create a new folder called etc. So you should have /usr/local/etc/ in your iPhone’s folder/directory structure.
8. Back on the iPhone, go to the Home -> Settings -> General -> Auto Lock and set it to Never (this is so that the WiFi connection does not drop during the process)
9. Now you have to run stuff on the iPhone. Open Terminal (Applications -> Utilities -> Terminal) and SSH into the phone by typing in ssh root@10.0.1.5 (this is your iPhone’s IP address – to find what it is go to Settings -> WiFi and click on the blue arrow next to your WiFi connection). The password is dottie. Then type in the following commands:
   1. cd /usr/bin/
   2. chmod +x bbupdater
   3. chmod +x iUnlock
   4. chmod +x minicom
   5. launchctl unload -w
   6. /System/Library/LaunchDaemons/com.apple.CommCenter.plist
   7. iUnlock ICE03.14.08_G.fls nor
10. Once that finishes, type in minicom
    1. After the application starts, type in AT S7=45 S0=0 L1 V1 X4 &c1 E1 Q0 and then return.
    2. No results were printed out on my screen but it worked.
    3. I was not able to quit minicom so I just exited the entire Term-vt100 by pressing the Home button and entering Term-vt100 again.
11. Type in the following command in Term-vt100
    1. launchctl load -w /System/Library/LaunchDaemons/com.apple.CommCenter.plist

That did it for me… put in my Brazilian SIM card from TIM and there I was roaming on T-Mobile’s network… Made a call and it worked. My AT&T card is also working – tested a call, SMS and the EDGE network.
Ufff!!
More information about this entire process with more detailed instructions and things to do if something goes wrong: http://iphone.unlock.no/
Also – this seems to be the wiki with the most up to date information – http://iphone.fiveforty.net/wiki/index.php/Latest_Progress_Report – there is a GUI app called anySIM that they released but it did not work on my phone – had to go the manual way described above.