As many of the people , I started using Alestic AMI which is quite popular among debian users . A simple apt-get update and upgrade gave me these issues .
Issue with locale .
dpkg-reconfigure locales will fix the issue if you select the proper local type and encoding .
en_US and UTF8 will do for most of the users ;)
Next issue was a bit major because it was not allowing me to install anything before initscripts was configured correctly , it was because of the scripts written by alestic guys . A google search on the issue gave me a debian bug http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=589238 The solution suggested there solved my issue .
All the scripts from Aelestic missed a initblock on the init.d scripts . Hence add a block like this
### BEGIN INIT INFO
# Provides: ec2-ssh-host-keygen
# Default-Stop: 0
# Short-Description: Generate new ssh host keys on first boot
# Description: Generate new ssh host keys on first boot
### END INIT INFO
After adding the lines for all the ec2 scripts in /etc/init.d/ and running dpkg --configure initscripts I could finish with my apt-get upgrade !