Android 6 Marshmallow introduces a new power saving feature, the so called "doze mode". 
At time of writing, there seems to be an incompatibility between it and our apps. When in doze mode, "the system does not allow sync adapters to run", but "periodically, the system exits Doze for a brief time to let apps complete their deferred activities. During this maintenance window, the system runs all pending syncs, jobs, and alarms, and lets apps access the network."  Obviously, the latter doesn't work properly. We don't know yet if it's bug in Android or in our apps, but we're investigating it further.
Fortunately, there is a workaround yet: Just exclude our apps from the doze mode at [Android settings->Battery->Battery optimization].
(Thanks to Will and Michael!)