Darn it. I decided to update my iPhone and didn't realize a new patch had just come out. I updated through the Apple site, it downloaded a 160 meg file, then borked my iPhone saying it needed to be restored. This was an iPhone that had never been updated.
The restore didn't work either. I'll have to keep trying.
Edit: 1 hour later. I updated iTunes, restarted my computer, plugged in the iPhone, and this time it restored and synced up.