I have the exact same problem. All links just load the index, no matter if it’s a link to a post, page or archive page.
I also tried to let WP create a new .htaccess, but that doesn’t do anything.
If it’s to any help, here’s the .htaccess it creates:
# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /blog/
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /blog/index.php
</IfModule>
# END WordPress
I have a test install running 1.5.2 at the same host, and since that could rebuild permalinks just fine I’m pretty sure it’s related to the new WP version rather than anything server side.