Comment 29 for bug 1888575

root@xenial-base-files:~# apt-cache policy ubuntu-server
ubuntu-server:
  Installed: 1.361.6
  Candidate: 1.361.6
  Version table:
 *** 1.361.6 500
        500 http://br.archive.ubuntu.com/ubuntu xenial-proposed/main amd64 Packages
        100 /var/lib/dpkg/status
     1.361.5 500
        500 http://br.archive.ubuntu.com/ubuntu xenial-updates/main amd64 Packages
     1.361 500
        500 http://br.archive.ubuntu.com/ubuntu xenial/main amd64 Packages

ubuntu-server 1.361.5, currently in xenial-updates, has grub-legacy-ec2 in the Depends line:

root@xenial-base-files:~# apt-cache show ubuntu-server=1.361.5|grep ec2
Depends: acpid, apport, at, bcache-tools, btrfs-tools, byobu, cloud-guest-utils, cloud-initramfs-copymods, cloud-initramfs-dyn-netconf, curl, ethtool, fonts-ubuntu-font-family-console, git, grub-legacy-ec2, ifenslave, lvm2, mdadm, open-iscsi, open-vm-tools, overlayroot, patch, screen, software-properties-common, sosreport, tmux, ubuntu-cloudimage-keyring, update-notifier-common, vim, vlan, xfsprogs, motd-news-config

But ubuntu-server 1.361.6 from proposed does not, as expected:
root@xenial-base-files:~# apt-cache show ubuntu-server=1.361.6|grep ec2
root@xenial-base-files:~#