You've probably already found an answer for this issue, but I will post this for any other person this becomes relevant for should this occur to you:
upon plugging the device into your computer/laptop, it will give the message you were stating. Do not allow it to sync to yur current library AT ALL. Rather, click onthe summary tab that displays when you've clicked on the iPod/iPhone on the left side menu bar. The summary and all over information will be in the right hand side of the screen.
Once you are in the SUMMARY TAB: click on the backup there are three rows: iPod, Version, and lastly, OPTIONS. There are four selection boxes. Click on the last box labeled "Encrypt iPod/iPhone backup" or you can also select this option by clicking on the change password box. Put in your iTunes account password--it seems to be synced that way and always works. If you are prompted to update iTunes software in the process, do it. It is better to have the updated version and have it function smoothly during this transition.
This will backup everything on your device without losing your information permanently.
Once this step is complete, you will indeed need to restore he device to factory settings. Please note, this is the only systematically correct method I know of to successfully re-register your device back into your library.
After factory settings are restored... TIME TO PUT YOUR MUSIC/Apps/Etc BACK IN.
This will take some time and your device will also be caused to shut off and restart on it's own.
A New screen appears asking you to set up your iPod/iPhone.
You will see the back up on your screen and should select the restore from back up option listed there. You will be prompted to install your password from the last time you backed up your computer (as stated before, this should have been the iTunes account password for the sake of consistency)
This backup too should take a few minutes.
You should be ready to go after this.