It took a while for me to solve this issue. I moved my small project Friended.com from GoDaddy 4GH hosting to AWS Amazon, then the permalinks stop working. I research, read, research and keep on searching, but can't find any information to resolve it.
Oh well, it took 6-8 hours of non-stop searching to fix the "wordpress permalinks not working".
In my new AWS Amazon hosting, I need to change the AllowOveride All, (from AllowOveride None). Restart the web service "service httpd restart".
Viola my wordpress permalinks start working ... come check it out, sorry for my shameless advertising please visit Friended.com website.