Clean URL mod_rewrite issues

I am working on enabling clean URLs, but this message is displayed whenever I go to the page:
Your system configuration does not currently support this feature. The handbook page on Clean URLs has additional troubleshooting information.
As far as I can tell, I just need to get mod_rewrite enabled. I started by posting on the Ubuntu forums, but the responces I got suggested that it could be a Drupal issue. Here is what I have tried:

apache2ctl -t -D DUMP_MODULES

This does not return mod_rewrite, although it returns lots of other modules.

sudo a2enmod rewrite

This returns: This module is already enabled!

I added this code to my /etc/apache2/httpd.conf:

<IfModule mod_rewrite.c>
RewriteEngine On
</IfModule>

I have changed this part of my /etc/apache2/sites-enabled/000-default:

<Directory /var/www/>
		Options Indexes FollowSymLinks MultiViews
		AllowOverride None
		Order allow,deny
		allow from all
	</Directory>

to this:

<Directory /var/www/>
		Options Indexes FollowSymLinks MultiViews
		AllowOverride all
		Order allow,deny
		allow from all
	</Directory>

In /var/www/lldrupal/.htaccess (lldrupal being the name of my test Drupal site), there is already this section (some comments have been removed, because they are very long):

<IfModule mod_rewrite.c>
  RewriteEngine on


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

Thanks!