I figured out that RewriteBase was commented out in the .htaccess file which was preventing 'Clean URLs' feature to work. The issue is fixed after enabling it.
# Modify the RewriteBase if you are using Drupal in a subdirectory or in a
# VirtualDocumentRoot and the rewrite rules are not working...