CodeDeploy agent install fails with Could not get lock /var/lib/dpkg/lock

I am trying to install the agent on Ubuntu 16.04 LTS

Like this:

wget https://aws-codedeploy-us-west-2.s3.amazonaws.com/latest/install
chmod +x ./install
sudo ./install auto

It fails to install. Looking at /tmp/codedeploy-agent.update.log I see that it is failing to install gdebi with this message:

Could not get lock /var/lib/dpkg/lock

This is running during cloud-init.

If I run it manually once cloud-init is done it installs fine.