So keep in mind that that there's a system cache that relates solely to the installed Android operating system on your phone, and then there are app caches that are used only by each respective app. All caches are just non-vital (don't retain important data) and temporary, but different processes running on your phone have to have them to function. When you booted up into your phone's Recovery, that involved wiping the system cache. There isn't a drawback in doing so (the system cache just gets rebuilt) but it's also typically not a necessary thing to do unless there's a reason to. Anyway, individual app caches are separate from the system cache and you need to use the Settings menu to manage them instead of booting up in to Recovery Mode. Try looking the Settings >> Apps >> Contacts app >> Storage menu. There should be options for Clear data and Clear cache (be careful not to inadvertently use Clear data instead, be sure to back up your contacts list first -- Export to vcf)
All that said, I doubt clearing the Contacts app cache is the actual source of the problem, it's just a standard thing to try when quirky app issues like this one pop up.
It doesn't to try though, and it might help.
At this point I'm out of suggestions on a fix. This is weird since things were apparently OK before and still are when syncing your other Google services, it's just Contacts. If you disable Contacts syncing in that Settings >> Apps >> Google menu and try to do a manual sync does that same error message occur? (... an option similar to 'Sync now' or words to that effect might be buried in a submenu or in an icon in the top or bottom menu bar.) Also, just to confirm are there indeed contact entries made after April 16th in your phone's Contacts app that aren't showing up in your online Google account Contacts (or vice-versa), or is it matter of syncing is working but there's just that error message stating otherwise?
