It appears that the recent qemu packages released for 16.04 set the machine type to "pc-i440fx-zesty" instead of "pc-i440fx-xenial". If you override this and make it use "pc-i440fx-xenial" instances boot again.
FYI, if you are using OpenStack, this can be done by editing nova.conf, [libvirt] section, and add hw_machine_type = x86_64=pc-i440fx-xenial
It appears that the recent qemu packages released for 16.04 set the machine type to "pc-i440fx-zesty" instead of "pc-i440fx-xenial". If you override this and make it use "pc-i440fx-xenial" instances boot again.
FYI, if you are using OpenStack, this can be done by editing nova.conf, [libvirt] section, and add hw_machine_type = x86_64= pc-i440fx- xenial