Brajeshwar just sent me an email saying it was ok with him to post the solution.
So, to solve the permalink issue, for the nishita theme in a windows server, the following worked for me:
1- under Options >Permalinks check, "Custom, specify below " and insert this in the custom permalink field: /index.php/%year%/%postname%/
2 - find your header.php file and replace whatever it is in between <!-- BEGIN #nav --> "replace here" <!-- END #nav -->
with the following code:
<!-- BEGIN #nav -->
title="<?php bloginfo('name'); ?>">Home
title="Entries RSS Feed">RSS Feed
<!-- END #nav -->
Now, that worked for me. again this applies for the nishita theme only, not sure this will fix the same problem with other themes... but it might not hurt to try.
if you want to go back to re-use one of the others themes such as the default theme, make sure you check default for the permalink structure for the other themes to work.
hope this makes sense.