Also will need to know what Baseband and Firmware you're running..
The problem is, is if you've bought a locked iPhone, and you're not using the correct SIM to the provider it is locked too, it won't let you get to the "Plug into iTunes to activate" screen.
I had this same issue. However, things may have changed, so I'll include the same instructions I followed, and hope they work for you.
First, restore your phone using an old firmware (3.1.2, or 3.1.3)
If you have iTunes 9.1.2 or higher, download Blackrain Fix from iH8Sn0w
Fix your Blackra1n file, if nessessary
Plug phone into computer, and run Blackra1n - this should hacktivate it and allow you to bypass the iTunes "Insert Correct SIM" screen.
To restore using a specific firmware, download 3.1.2 or 3.1.3 onto your computer from FelixBruns. Then, add the following line to your hosts file, located in your windows directory, then System32\Drivers\ETC\
Lastly, hold SHIFT and click the "RESTORE" button in iTunes and select the firmware file you downloaded above.
Please be aware though, this custom restore function will only work if the previous owner added his SHSH blobs to the Cydia source when he jailbroke it. If he didn't, you're boned and will have to wait until the jailbreak and unlock solution comes out, which is expected at the end of July 2010 for 4.01.