It's a problem with Outlook. Try the repair function in Outlook. Then run scanpst.
Then try deleting partnerships on phone and PC with soft reset of phone and reboot of PC. Then remaking partnership. Backup contacts with PIMBackup b4.
If none of those work, you might have to mess more with the .pst file:
http://support.microsoft.com/kb/829971
Archive off your old .pst file b4 creating new to avoid data loss.