Back up everything (photos, music, sms/mms, etc). Do an FDR and restore your data. Yes, it is a lot of work, but should always be done when updating a phone. I very rarely have issues when I follow this path.
I have had this issue for 2 weeks. Cleared cache, data, force stopped contacts and shut down phone. It's been 5 days and it hasn't come back yet. Fingers crossed as it was really annoying.I get this on the note 4 as well. It's been suggested to clear datat, clear cache, even go into calendar and turn on contact sync. It's my personal opinion that it's a software bug. I've seen more then 20 posts and reports of the same thing between the galaxy and the note series.
Sent from my Note 4