A little backround: I am a complete idiot. I am currently in Colombia and 1.5 years into a round the world drive. I have an AT&T iphone 3G and a MacBook. I am also not the most tech adept person you can find...

The problem: I have an iPhone 3G that I jailbroke and unlocked about a year ago. I have been using it with no problems with the sim cards from several carriers of several countries in Latin America, but lately I have been experiencing lots of freeze and crashes so I decided to erase, upgrade and start from scratch. I connected to iTunes and requested a restore... problem is I forgot one major detail, i do not have the AT&T sim card anymore. Now the iPhone is locked and requests a connect to iTunes and iTunes in turn requests a compatible sim card

Any ideas? Please.

Originally Posted by LostWorldExpedition

I connected to iTunes and requested a restore...

This step was quite stupid, well - to be honest "erase all content and settings" is 99% of the time a very stupid option to choose.

You are somewhat lucky because you have a 3G iPhone (not newer) and you have access to a mac. If you have truly restored to iOS 4.2.1, then the following two guides will fix your problem. The third step is optional (but highly recommended)

iClarified - iPhone - How to Jailbreak and Unlock Your iPhone 3G Using PwnageTool (Mac) [4.2.1]
iClarified - iPhone - How to Unlock the iPhone 4, 3GS, 3G Using UltraSn0w
iClarified - iPhone - How to Hactivation Your iPhone Using Subscriber Artificial Module (SAM)

I suggest you read the three posts that follow to get an idea of the potential problems you will experience with this technique (if you want unlock, you don't really have many other options - yes you can use redsn0w 0.9.rc8, but you will need pwnagetool custom IPSW the next time you want to restore the phone, so you might as well make one now while you have your mac handy)

http://www.hackint0sh.org/f204/196391.htm
Dev-Team Blog - Ultra-recycle
Dev-Team Blog - Thanksgiving with Apple