When you configure your permalinks within WP, at the top of the page does it say successful or does it say you must now update your .htaccess file?
I had a similar problem and all I had to do was put an .htaccess file in the root directory of my blog – the one that sits in the root directory of the site is not the one that was being modified.
You also want to make sure this file is writable.
Hope this helps.