Everything.
Not everything is backed up.
I had my phone replaced shortly after I bought it, and when I restored the original settings to the new phone, I lost all my photos and all my notes. I don't think I had the calendar set up yet, but losing the notes really annoyed me.
Hmmm....I don't think ,my backup was corrupted, but it is possible. This was also before the 2.2 software upgrade, so maybe this funtionality was added then.