It *could* be Sprite...I always use a combo of Outlook and MyPhone without problems. I know other folks in the past have reported issues with Sprite backups, so I've always steered away.

Did you happen to sync your contacts with MyPhone? ...a looooong work around would be to flash a version where you last had it working, back up with MyPhone [cooked into the ROM], flash back to what you're currently running, and import.

I mean, I could see the potential for error if you were going from a PIM backup in 2.1 to a restore in 2.5...maybe there's some conflict there? Sorry I don't have better information on this.