Hi I ran into this problem too and I’m on Brinkster Windows hosting. The permalink I’m using is:
/index.php/archive/%postname%/
After upgrading from v2.2 to v2.5, none of the links to either posts, pages, categories or calendars work. However, when I change permalinks back to the default setting, everything goes back to normal. Now I’m pretty sure it’s got nothing to do with my hosting provider as custom permalinks were working on the older version.
Anyone have any idea on what else I can try? I tried using the modified rewrite.php by dlo but had no joy with it. ??