The solution:Settings –> Applications –> Manage Applications –> All (button on the top that lets you see all applications) –> scroll down to “Contacts Storage” –> Click on “Clear Data”