Contacts screen frozen

I recently updated my Samsung Galaxy SII to 4.0.4. After the upgrade there were only 64 contacts on my phone but I was able to scroll through the contacts. Before the updatet though, there were hundreds of contacts. I tried a trial version of a 3rd party software called Android-Sync and it successfully transferred the maximim # of contacts with the trial version (20) and I could still scroll on the contacts. When I loaded the full version of Android-Sync, my contacts were stored to my phone but now I cannot scroll in the contacts screen. Receive a message that it is not responding do I want to Wait or Cancel. Neither option unfreezes contacts. Have unistalled the Android-Sync app and still can't unfreeze contacts. Phone has been shut down several times with no luck. Android-Sync says its not their problem. Any ideas?