If you are using Android 6.0 there is a "new feature" that cancels synchronizers if they don't perform any network activity for a certain period of time (see here and vote to get this resolved).
The result is that the sync will stop with a red sync icon and only repeatedly retriggering the sync will eventually cause the synchronization to succeed.
If you have Android 6.0 or higher and are suffering from this issue, you can disable sync cancellation in the settings screen:
Note that turning this "workaround" on will also ignore other cancellations of the synchronization (e.g. when the phone is shutting down or when the user tries to cancel a hanging synch), therefore use this only if you must.