I am having this problem also. The phone is not stolen. I work for AT&T and was given a demo model of the phone back during the initial release, along with several coworkers.
Just to give a little background.
Initially, I had an issue with my iPhone with the most recent iTunes and iPhone software update. After downloading the new update completely, when iTunes went to install the device software, everything froze during installation. My computer first lost internet connectivity, then completely froze to the point where I could not do anything, including accessing Task Manager to kill the unresponsive program. I ended up having to restart the computer, even though the iPhone software did not completely install. When the phone booted back up, I got a message that the phone was in "Restore mode" and could not be used until restore was completed. When I would plug in to restore the device, everything would freeze up again, forcing me to reboot the pc again. I then tried to uninstall iTunes, but kept getting a message that the uninstaller could not find iTunes.msi. I was able to correct this by syncing my iPhone with another iTunes account, and the uninstalling iTunes with a clean uninstaller.
Now my iPhone issue is completely resolved. My phone is back up and running, and iTunes is installed on my computer and everything is working.
Now, moving on to my coworker who came to me this morning with his iPhone problem. He tried to update the iTunes and iPhone software last night. His phone is password protected, as is company policy.
On the standby screen, it shows the iTunes cable, says slide for emergency, etc... When I cradle the device, I get a pop up message that states "iTunes could not connect to the iPhone because it is locked with a passcode. You must enter your passcode on the iPhone before it can be used with iTunes."
Please listen and pay attention everyone. When I slide the bar that says "Emergency Calls Only" it goes to a keypad, and never gives an option to enter the lock passcode. That is the problem. If it would prompt me to enter the passcode, I could enter it, and all would most likely be resolved, but I don't get that prompt.
I have tried forced restart holding the home and top button for 20 seconds, past the point where it says to slide to power off. Same thing happens. I have tried syncing with a different pc, something that worked for my problem, but is not working for my coworkers.
I am not sure what else to try. If all else fails, I may try to jailbreak the device as it is out of warranty, so Apple will not replace it.