Was having some odd problems with my iPod touch (16GB, v1.1.3 with January software upgrade) occasionally changing the date and time to Dec. 31, 1969, also getting stuck in caps lock mode, so I decided to restore.
First attempt at a restore failed. Second attempt looked like it succeeded, with a message that came up after the firmware restore that said the iPod would reappear in iTunes after it finished restarting. After a long wait, the iPod restarted with the "connect to iTunes" image, then went black. A short time later, a window popped up with the message about the missing pairing record.
Two, three or four attempts at disconnecting and reconnecting the cable all resulted in the same error message. I started writing this post, in fact, to report I was stuck with the same unusable iPod, when I reconnected the cable to make sure I had the wording of the error message correct.
Wouldn't you know? It connected just fine, asked me if I wanted to restore my settings and at the moment is syncing back all my music and movies. I'll return here if I see any more problems, but I'm keeping my fingers crossed that all's well.