Links stopped to work. Any links go to main page.

After my hosting provider migrated to new server, the links in all of my WordPress blogs stopped to work.
I mean links to categories , archive , rss feed etc… When I click on links I go to main page http://example.com/myblog/ .
I know that by eliminating in my ‘permalink structure’ /index.php
(going from the following: /index.php/%year%/%monthnum%/%day%/%postname%/
to the following: /%year%/%monthnum%/%day%/%postname%/),
I get the links working again but my rss feed
http://example.com/myblog/index.php/feed/ would not work. I should change it to http://example.com/myblog/feed/ ,
but doing that I would lose the current subscribers (them subscribed http://example.com/myblog/index.php/feed/).

Could anybody suggest me any solutions? (my WP version is 1.5.2)

Thanks