Just to elaborate a bit.
The CF template specifies two EBS drives for the masters:
But only one for the Agent nodes:
But the cloud-config.yaml for the CoreOS nodes expects there to be a /dev/xvdb:
In CoreOS 1632 (not clear if this is an issue on earlier version), the units added by the cloud-config end up part of the systemd dependency string for systemd-timesyncd:
It seems there is some kind of race condition on initial install of these machines - it looks like the time service is able to start before the cloud-config.yaml adds the var-lib.mount unit. It is only on a reboot that the problem shows up (since the units are on the disk at that point and don't need to wait for cloud-config to lay them down.
Two possible fixes: Add a second volume to the slaves (this would use more resource but would match our recommendations to put var/lib on separate spindles) or perhaps only apply the extra cloud-config.yaml to master node.