Problem is that /etc/machine-id has label system_u:object_r:unlabeled_t:s0 which basically means that it has label kernel does not understand. Instead, it should have label system_u:object_r:machineid_t:s0. Running restorecon should fix your problem.
I'm closing this as WORKSFORME for now as I haven't seen this kind of issue lately. In case you are still able to reproduce with latest bits (both systemd and SELinux policy) please reopen the bug.