Comment 4 for bug 1594576

I now think this could be a conflict between cloud-init and systemd-triggered apt actions.

If apt-daily.service is triggered before cloud-init, any apt actions that cloud-init takes will fail. See this discussion for more info and a possible solution:
https://unix.stackexchange.com/questions/315502/how-to-disable-apt-daily-service-on-ubuntu-cloud-vm-image