After some digging, T141673 appears to be in the labvirt layer, with instances just not doing any IO and being stuck. A bunch of experiments me and @chasemp did lend a lot of credence to this theory. We should try to upgrade the qemu-system-x86 package, which provides /usr/bin/kvm (via a symlink created in puppet) and see if that makes the problem go away.

It is currently at version 1:2.3+dfsg-5ubuntu9.4~cloud0 across the fleet, which is the latest available in the Ubuntu Cloud repos for Trusty. They're up to 2.6 now in the latest release (Yakety?) and 2.5 in the latest LTS (Xenial).