Performing the steps you listed should correct the issue.
We can get complex if you like though ;)
How many email address are set up on the Blackberry? Are they BIS, BES, Redirector?
If you go into Settings>Options>Advanced Options>Service Books. Are there any entries for Desktop [CMIME] and Desktop [CICAL]?
It could be with the back up and restores performed that you may have multiple CICAL service books, which can funk up the calendar. If on BIS, than each email will have a 2 service books: one CMIME and one CICAL. If multiple CICAL's appear for an email address delete each of them and resend them from the BIS site.
Working for the dark side (AT&T) and fixing PDA/Blackberry issues since '03.