Acabei de testar hoje na AMI da AWS. O mesmo problema no começo ao tentar instalar a gema sqlite3. Tentei como dito pelo instalador, sem sorte. No entanto, eu tentei
sudo gem install sqlite-devel
e funcionou, poderia instalar a gema sqlite3 depois disso ...
Espero que ajude.