Короче, проблему решил в итоге без правки каких-то шаблонов. Суть проблемы была в том, что systemd долго ждал сеть. Хотя по факту сеть была поднята (по крайней мере ipv4). Решением было добавление
optional: yes
в 50-cloud-init.yaml
Но, внезапно было выяснено, что если не отключать ipv6 в sysctl, то и так всё ок работает. Короче, в бубунту в очередной раз завезли какую-то хрень.