I found out that if u used the spirit jailbreak on ur 3GS and then restored off ur backup onto ur new iphone 4, then this causes problems when updating software... The info below helped me out as well... Also using the apple cord that came with the new iPhone or iPad also seems to be neccassary.
Originally Posted by nicksherb
Hey I had the same problem, while beta testing 4.0 whats more so I was very worried. However, turns out you just need to uninstall itunes and some core files
If you are still unable to restore iPhone, remove iTunes by doing this:
If you are a Mac user, delete the following files:
2. /System/Library/PrivateFrameworks/DeviceLink.framework
3. /System/Library/PrivateFrameworks/MobileDevice.framework
After that, restart your Mac and install the latest version of iTunes. Repeat the normal restore again.
For Windows users, uninstall Apple Mobile Device Support and iTunes from your system, restart the computer and re-install the latest version of iTunes from apple.com and try to restore again.