iTunes randomly thinking my iPhone/iPad is "new"
Completely restore the iPhone using DFU mode.

See the instructions posted on this website and then do a complete restore of your iPhone and set it up as new.

If the problem persists, it might be that your iTunes would need to be reinstalled. Don't forget to unlink your library to your computer before uninstalling iTunes and keep a copy of your data.

Consolidate your library PRIOR to backing it up, removing iTunes, etc., etc.