I know!
After the Galaxy S4 update, if you get the "Unfortunately contacts has stopped" error, you need to force the call history to be erased. I found this by debugging the phone (I was supposed to write a app for my company, so I learned some stuff.) and saw that the phone app was asking the contacts app for call history and it crashed. I took a guess that erasing the call history might do something.
Bad news is that I couldn't find how to erase the call history from the contacts app (which is where its kept). Erasing call history is done from the phone app, but it crashes when you try to access the menu. Maybe you can find a way to do it. I couldn't.
Good news is that I erased the call history using a different contacts app. I installed "Contacts +" used it to erase the call history.
Tada! No more crashes.
Hope this helps others.