I dunno which of these steps fixed the problem. But, I did fix it, thanks to everyone here.
I deleted and re-installed iTunes. Then, I deleted the library files as described .
Still didn't work.
So, I ran redsn0w 0.8 again... Amazingly, the iPhone was now jailbroken!
Still didn't sync with iTunes though.
Deleting the same library files again didn't work.
Installing iTunes as a new user on my computer let me sync my iPhone again.
Deleting the library files created for the new user, let me restore and sync my old iPhone without the contacts.
Opening MS Outlook gave me a list of all of my old contacts. I was able to type them in manually.
Using the Microsoft Camera & Scanner Wizard restored a seemingly random selection of my photos. However, the camera roll does not show previews for the restored photos. Instead, the screen shows all black when I look at the camera roll. I can scroll up and down the blackness. Wierdly, tapping a section of the blackness, shows a photo, and lets me scroll through the rest normally. However, the previews are not generated correctly.
Everything's back to normal now! Sorry it took so long to reply... Thanks for the help!