CodeIgniter based website responds with 404 error after moving to another hosting

Greetings, everyone.

I've recently moved one of my old sites to a new hosting at Goddady's virtual server. I've copied its database, changed several strings in config.php and database.php CodeIgniter's configuration files which contained urls related to old hosting. Site's homepage opens successfully, but any other pages display 404 error. Site still works ok at old hosting.

Algorithmically, it should work as this: if page other than index.php at root dir is requested, modrewrite (rules are specified in .htaccess file) kicks in and substitutes requested document with index.php, then hand off this requested document as a parameter (after "?" sign) to the index.php; index.php than supposed to route request to the codeigniter engine, which should serve requested page. Thats where, I presume, issue happens.

Can you point out what possibly I could do wrong?

Thank you in advance.