I had the same problem. Find the original location of your .htaccess file and change the permissions/CHMOD to 666. That should solve your problem – it did mine. Alternatively, you can add the code that WordPress 1.5 gives you at the bottom of the page, after you update your permalink structure, to your .htaccess file. either way, your problem should be solved quickly. Hope this helped.
