Did you do a full backup of your iPhone prior to installing iOS 5? If so did you allow it to do a full restore? Also, are you using GMAIL for your contacts or some other storage system instead of the built in system?
Yes I did a backup before updating and I restored the phone from the backup but the problem insists. Unfortunately Iam not using Gmail for my contacts.