This is one of the most popular solutions to fix this problem without a factory reset. It is to go settings ->application manger -> all-> and clear data on contact and contact storage in app manager. This will fix the problem.
But... Your data for contacts will be wiped away. So remember to BACKUP!