Clean urls not working on Linux hosting

I have installed Drupal 7 on Linux hosted server (Shared Hosting). However, for some reason i am not able to enable clean urls. I have tried possible solutions that i have come across through out the drupal community, but no luck.

I keep getting an error saying "The clean urls test failed"

I have tried making the required changes in my .htaccess file as well.

"#
# Apache/PHP/Drupal settings:
#

# Protect files and directories from prying eyes.

Order allow,deny

# Don't show directory listings for URLs which map to a directory.
Options -Indexes

# Follow symbolic links in this directory.
Options +FollowSymLinks

# Make Drupal handle any 404 errors.
ErrorDocument 404 //index.php

# Force simple error message for requests for non-existent favicon.ico.

ErrorDocument 404 "The requested file favicon.ico was not found.

# Set the default handler.
DirectoryIndex index.php

# Override PHP settings. More in sites/default/settings.php
# but the following cannot be changed at runtime.

# PHP 4, Apache 1.

php_value magic_quotes_gpc 0
php_value register_globals 0
php_value session.auto_start 0
php_value mbstring.http_input pass
php_value mbstring.http_output pass
php_value mbstring.encoding_translation 0

# PHP 4, Apache 2.

php_value magic_quotes_gpc 0
php_value register_globals 0
php_value session.auto_start 0
php_value mbstring.http_input pass
php_value mbstring.http_output pass
php_value mbstring.encoding_translation 0

# PHP 5, Apache 1 and 2.

php_value magic_quotes_gpc 0
php_value register_globals 0
php_value session.auto_start 0
php_value mbstring.http_input pass
php_value mbstring.http_output pass
php_value mbstring.encoding_translation 0

# Requires mod_expires to be enabled.

# Enable expirations.
ExpiresActive On

# Cache all files for 2 weeks after access (A).
ExpiresDefault A1209600

# Do not cache dynamically generated pages.
ExpiresByType text/html A1

# Various rewrite rules.

RewriteEngine on

# If your site can be accessed both with and without the 'www.' prefix, you
# can use one of the following settings to redirect users to your preferred
# URL, either WITH or WITHOUT the 'www.' prefix. Choose ONLY one option:
#
# To redirect all users to access the site WITH the 'www.' prefix,
# (http://example.com/... will be redirected to http://www.example.com/...)
# adapt and uncomment the following:
# RewriteCond %{HTTP_HOST} ^example\.com$ [NC]
# RewriteRule ^(.*)$ http://www.example.com/$1 [L,R=301]
#
# To redirect all users to access the site WITHOUT the 'www.' prefix,
# (http://www.example.com/... will be redirected to http://example.com/...)
# uncomment and adapt the following:
# RewriteCond %{HTTP_HOST} ^www\.example\.com$ [NC]
# RewriteRule ^(.*)$ http://example.com/$1 [L,R=301]

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

# Rewrite URLs of the form 'x' to the form 'index.php?q=x'.
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond %{REQUEST_URI} !=/favicon.ico
RewriteRule ^(.*)$ index.php?q=$1 [L,QSA]

# $Id: .htaccess.in,v 1.1.1.1 2008/10/02 09:13:43 ilobachev Exp $"

Please let me know if i have to make any further changes in my .htaccess file to get clean urls working. I have installed drupal on root and not in a sub directory.

I have contacted my host and according to them url rewrite is enabled on the server. Any help on this issue will be highly appreciated.

If you all want any other instructions from my side to fix this issue then please let me know.

Thanks in advance. Hope someone over here might be able to help me out.