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!)
Update: It seems to affect Google's own apps as well, what makes it a bug on Google's side.   In reaction, Google already started to roll out an OTA update (6.0.1 build MMB29Q) for Nexus devices containing a fix.
Doze mode settings on Samsung devices: https://www.verizonwireless.com/support/knowledge-base-204545/