IPhone – Unfamiliar prompt when inserting new prepaid SIM card into iPhone in China

This is, unfortunately, expected behavior. Whenever you activate an iPhone (which you do as part of an OS install) it talks to Apple's servers and does various things like exchange crypto certs for APNS, etc. It also checks the IMEI of the phone to see what carrier Apple sold it to, and validates the SIM is valid for that carrier (if you buy an unlocked iPhone in a country where you can buy either locked or unlocked phones the vendor will actually copy down the IMEI number of a normal locked phone, and then enter in their system where it gets pushed to Apple's servers as an unlocked phone, there is no physical or configuration difference on the phones).

The easiest way to get it activated is (as you surmised) to use an AT&T SIM. You mentioned you have an iPhone 4, you can activate it with that SIM. There are plenty of companies that sell microSIM to SIM adapters, but if you want to do it right now you can just place the micro SIM directly in the iPhones 3GS's SIM try with tape. I would not recommend doing this on a device you intend to keep the SIM in for a an extended period because the SIM is likely to come loose (and jam the SIM tray), but if you are just inserting it, activating it, and removing it you should be fine so long as you are pretty careful with how you apply the tape and not shaking the phone too much.

This is actually a pretty complicated problem with not enough detail to know which one of many things is causing the failure so I'll go over some basics:

1. Your phone needs to be activated through iTunes after a restore - so something in that restore process didn't work.
2. The sim and phone have three components - any of which can fail.
3. The activation process is complicated and has a lot of checks to be sure the image you are installing is not modified so that the phone will work as designed. This activation needs to connect to the internet so even when everything under your control is correct, it still fails from time to time. Problems on your computer with iTunes or the system itself can cause this to happen on an otherwise working phone.

I'm also going to assume the phone is locked to AT&T to keep things simple. If the phone is unlocked legitimately through the carrier and officially recognized by iTunes' activation process this is much more complicated. If it's otherwise modified, the complication is really much more involved so I'll leave those out of the discussion.

Looking at #1 above - the best advice is to reseat the SIM card and then try again to make sure it wasn't a timing or contact alignment issue. Considering #3 above - it's simplest to take your device to a totally different computer and try the restore there - you can always take it back to your computer to put the backup on it once it's working.

Let's look at #2 in more depth - sim and phone. A bad sim will cause this - you'll need to get another SIM to test this and replace the SIM with one active from your carrier if it's the cause.

Have you tried another SIM from your carrier - it doesn't have to be attached to an active contract or active line - it just has to be working. Try to rule out that the sim itself is bad or has failed. A good SIM will get you to "waiting for activation" and a full restore so you can copy apps to the phone and otherwise use it on WiFi. Putting your SIM in another phone can help know that your SIM is not bad, but it has to work in your phone, so you may need to get another SIM even if yours works in another device.

Once you rule out the SIM - you'll need to rule out software. Do another restore of the phone following this knowledge base article. If that doesn't work, force the device into restore mode to get the software loaded properly. Be sure there's not a failure in the restore process or you'll be wasting time on SIM olympics or getting your phone swapped.

That's the third part of #2 - if your phone has a failure (dust or dirt, contact problems, moisture or corrosion on the inside that is causing the circuitry to break, or just a random electrical failure) you will need to get it in for service. There a technician will have the tools (otoscope, test rig, test SIM, good software to restore your device) and the training to know what worn contacts look like to know if it's a cleaning/reseat issue or a hardware repair is needed.