Samsung Galaxy S5 Mini — "sync is currently experiencing problems, it will be back shortly"

Hello,
Lately my contacts disappear couple of times a day. The only way to get them back is to reboot the device. I have a Samsung 5S mini (SM-G800F). I was looking in the acounts settings, and I usually see the message in the topic in the bottom, and have a failure sign next to the contacts sync. I've looked this problem up online for a long time, and have tried lots of stuff. I've cleared cache and data for practically alsmot everything related to google services and contacts. I've also tried the Contacts Sync Fix app, and resetting preferences for all applicatios. Nothing seems to work.
I figured out I lately also have this 2 messages appearing from time to time (have followed instructions to get rid of them, but didn't work either):
"Unfortunately, the process android.process.acore has stopped"
"Unfortunately, the process com.google.process.gapps has stopped"

Is there anyone with a good solution to this? It drives me crazy

Thanks for the reply. I was afraid that would be the solution.
More on that: The Kies program on my PC suggested me to use Smart Switch. Do you know of any significant difference between the two?
Also, I see that the backup over there is pretty comprehensive. If my phone is buggy because of certain apps or configurations, isn't there a chance that the back up will bring it back with it?

Thanks

So, I did a factory reset. 2 days later started having this problem again.

Wpaajhn

Do not add new contacts on your samsung phone !!! It is so important to use recovery app at first !

Can you please explain? What I did is factory reset and then I restored basic stuff with Smart Switch (apparently it replaced Kies for my model and did the job). I got all my contacts backs simply by logging to my Google account. What should have I done differently?

Please? I'm desperate. I just figured out that my gmail app is syncing super slow too