WP 2.5?

[papagmp]

OK - Maj Stress and I are done stressing out on this one - here is the fix:

Create a empty .htaccess file in the WordPress root folder.
Use chmod (or your ftp) to set permissions on the htaccess to 777
Set permalinks to: /%category%/%postname%/

Note: /index.php/%category%/%postname%/ did not work for me in WP 2.5



See also: http://codex.wordpress.org/Using_Permalinks

If you already have an .htaccess file in the root folder, you should be able to just change the permissions.