I was doing a few things wrong. First, I didn't have the latest binutils installed.
This particular error, however, was the OOM killer at work. The peak RAM used during installation is greater than that of EC2 micro instance. Use a larger instance or use swap:
SWAP=/tmp/swap
dd if=/dev/zero of=$SWAP bs=1M count=500
mkswap $SWAP
sudo swapon $SWAP
This will swap in 500 MB, which was ample for my installation.