This is a copy from Philip Oakley’s blog. I just want to say thank you for helping me with the same problem. Here is a direct link to his blog posting.
http://philipoakley.org/2010/07/27/wordpress-2/wordpress-permalinks-not-working-on-ubuntu-10-04-mod_rewrite-issue-requires-a-symlink/
1. First we need to check if the rewrite module is installed. I was connected to my VPS server via SSH but either in a Terminal or via SSH type (or copy from below):
apache2ctl -M
This should show a list of Apache modules. Rewrite_Module should be there (as it is a default in Ubuntu 10.04) but if not check with your FTP client or in your file browser that /etc/apache2/mods-available contains a file called rewrite.load. If it does not then you need to fix this before you can carry on.
Presuming it does exist then we need to create a symlink
cd /etc/apache2/mods-enabled
sudo ln -s ../mods-available/rewrite.load
2. Now we need to check that rewrite module rewrite.load is in the mods enabled folder (/etc/apache2/mods-enabled). The easiest way is to have a look at that folder with your FTP client or file browser.
3. Presuming you are still OK then then the final and very import stage is to ?Enable AllowOverride All?
In the folder /etc/apache2/sites-enabled you should find a file called 000-default and you need to check that all permissions are set to read & write not just read only, easily done with an FTP client (right click file>File Permissions in Filezilla)
In 000-default it will probably say AllowOverride None in several places. Find the one for where you?ve installed WordPress , and change it to AllowOverride All. e.g if WordPress is installed at var/www/????? then it may be under the Directory ?/var/www? grouping.
Finally, dont forget to restart Apache from the terminal:
/etc/init.d/apache2 restart