I tested a precise cloud image to learn the apt-behaviour with the needed
packages. I confirmed precise images just use precise updates and has
very old-cloud-utils.

    apt-cache policy cloud-utils
        cloud-utils:
          Installed: 0.25-0ubuntu5.1
          Version table:
         *** 0.25-0ubuntu5.1 0
                500 http://joyent.archive.ubuntu.com/ubuntu/ precise-updates/main amd64 Packages
                100 /var/lib/dpkg/status
             0.25-0ubuntu5 0
                500 http://joyent.archive.ubuntu.com/ubuntu/ precise/main amd64 Packages


Adding cloud-archive:tools provides what we want, but update, upgrade will
not update cloud-utils. It is held back possibly because of conflicts.

    sudo add-apt-repository cloud-archive:tools
    sudo apt-get update
    apt-cache policy cloud-utils
        cloud-utils:
          Installed: 0.25-0ubuntu5.1
          Candidate: 0.27-0ubuntu9.1~ctools0
          Version table:
             0.27-0ubuntu9.1~ctools0 0
                500 http://ubuntu-cloud.archive.canonical.com/ubuntu/ precise-updates/cloud-tools/main amd64 Packages
         *** 0.25-0ubuntu5.1 0
                500 http://joyent.archive.ubuntu.com/ubuntu/ precise-updates/main amd64 Packages
                100 /var/lib/dpkg/status
             0.25-0ubuntu5 0
                500 http://joyent.archive.ubuntu.com/ubuntu/ precise/main amd64 Packages

    sudo apt-get upgrade
        Reading package lists... Done
        Building dependency tree       
        Reading state information... Done
        The following packages have been kept back:
          cloud-utils iproute isc-dhcp-client isc-dhcp-common linux-headers-virtual
          linux-image-virtual linux-virtual
        The following packages will be upgraded:
          bind9-host dnsutils file krb5-locales landscape-client landscape-common
          libbind9-80 libdns81 libgssapi-krb5-2 libisc83 libisccc80 libisccfg82
          libk5crypto3 libkrb5-3 libkrb5support0 liblwres80 libmagic1 libudev0 mountall
          ntpdate procps python-apt python-apt-common python-twisted-bin
          python-twisted-core python-twisted-names python-twisted-web tzdata udev
          update-manager-core

But if we ask to install BOTH cloud-utils cloud-image-utils we get the right
version.

    sudo apt-get install cloud-utils cloud-image-utils
        Reading package lists... Done
        Building dependency tree       
        Reading state information... Done
        The following extra packages will be installed:
          cloud-guest-utils distro-info distro-info-data gdisk genisoimage libaio1 libicu48
          libnspr4 libnss3 librados2 librbd1 python-distro-info qemu-utils
        Suggested packages:
          shunit2 wodim cdrkit-doc
        The following NEW packages will be installed:
          cloud-guest-utils cloud-image-utils distro-info distro-info-data gdisk
          genisoimage libaio1 libicu48 libnspr4 libnss3 librados2 librbd1
          python-distro-info qemu-utils
        The following packages will be upgraded:
          cloud-utils
        1 upgraded, 14 newly installed, 0 to remove and 36 not upgraded.

And asking for every package that I know we want installed upgraded also
installed what we want without removing anything.

sudo apt-get install cloud-utils  bridge-utils cloud-image-utils cpu-checker distro-info distro-info-data genisoimage libaio1 libnspr4 libnss3 librados2 librbd1 msr-tools python-distro-info qemu-utils rsyslog-gnutls