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 properly.
# For example if your site is at
http://example.com/drupal uncomment and
# modify the following line:
# RewriteBase /drupal
#
# If your site is running in a VirtualDocumentRoot at
http://example.com/,
# uncomment the following line:
# RewriteBase /