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.