Here are my assumptions:
1. You are running an Ubuntu server (anything at or after 8.10)
2. You are running WordPress 2.7+
3. Your basic install is working. Only pretty URLs are not working.
4. You have tried everything under the sun. Still no results.
5. You have deleted and recreated your .htaccess at least three times. No results.
6. This is not the first blog entry you are reading. (If it is, please try others first.)
Is your server reading the files?
Make sure that your server is reading the .htaccess files. A good way to test this is to put some garbage in the .htaccess file and read the server log (usually error.log) If your server is reading .htaccess file, then you will definitely see a mention in the error log that there was a syntax problem in the .htaccess file. This trick comes straight from the online apache manual.
My guess is that even after you put some garbage lines in the htaccess file, the errors are still the same for same pages. In other words, the types and description of errors have not changed after changing the htaccess file. If this is true, then you can be sure that Apache is not reading your .htaccess files. Our goal is to make apache read it.
If you are using a standard apache2 install on Ubuntu, just make sure of two things.
First: Check your AllowOverride
Make sure that AllowOverride All is setup correctly for your document root directory. If you are setting up a virtual server, this directive will go in one of the config files under your sites-enabled/ directory. Just put the following inside the Virtual Server block:
After adding this block, restart your server and try the wordpress pages. If .htaccess is still not being read, then you need to follow just more step.
Second: Check your mod_rewrite
Under /etc/apache2/mods-enabled, you are missing rewrite.conf. Stay within this directory and enable mod_rewrite like this:
sudo ln -s ../mods-available/rewrite.load ./rewrite.conf
Restart the server and you are all set. If it still doesn't work, try deleting the .htaccess one last time and try restarting your browser just to make sure you are not caching old pages.
Let me know if that works for you.