Looks to me like there may be a problem with the Ubuntu EC2 mirrors. After a fresh apt-get update, I'm seeting this:
$ apt-get install -yq git
E: Unable to locate package git
After a few more apt-get
's, it will often succeed.
Update apt-get
packages, run the following command:
$ apt-get update