Amazon Elastic MapReduce instances does not have the debian-multimedia sources by default, you can add the below to a bootstrap script to have it installed:
sudo sh -c "cat >> /etc/apt/sources.list << EOF
deb http://www.debian-multimedia.org squeeze main non-free
deb http://www.debian-multimedia.org testing main non-free
EOF"
gpg --keyserver hkp://pgpkeys.mit.edu --recv-keys 07DC563D1F41B907
gpg --armor --export 07DC563D1F41B907 | sudo apt-key add -
sudo apt-get update
sudo apt-get -y --force-yes install lame libmp3lame-dev faad
