Looks like you may have solved the problem - I had a similar problem where permalinks would not work, but the default links did work. I modified the .htaccess file to what Wordpress said to do. Twice I thought I had solved the problem, but didn't.
I had moved it to my local Ubuntu Karmic Koala system for testing, and found that the solution involved editing a file in /etc/apache2/sites-enabled. On my system, it was called 000-default.
This file had statements like the .htaccess file, and in two places had AllowOverride None, which I had to change to AllowOverride All. Apparently, this file overrides any local .htaccess files.
I also had to change the location of Wordpress in the main configuration, but that was obvious.
I hope this will help someone who has tried all the normal suggestions like me, and is still having problems.