Php as CGI problem! Help Please!

Here I have a problem which occured out of the blue:-(

I have been running a number of Drupal sites (mostly 4.0.0 and one 4.2.2 version) on a reseller hosting account with www.sultanhost.com. So far everything was smooth and I had clean URLs and Url-Aliases running with no problem.

Yesterday I found out that none of my Drupal sites were viewable. I immediately contacted them obviously and found out that they switched from PHP as apache module to CGI:

Here is their announcement on the support site:

Due increased number of MySQL connections on the server initiated by nobody user (php default user) we are going to change php run method from mod_php to cgi and remove abusing users.

CHANGE WAS TAKEN PLACE ON 20th OF OCTOBER AT ALL SERVERS.

There are some guidances you should to follow to feel safe about this move, don't worry if it looks too complex, in general all will be smooth:

1. User executing the wrapper must be a valid user on this system.
2. The command that the request wishes to execute must not contain a /.
3. The command being executed must reside under the user's web document root..
4. The current working directory must be a directory.
5. The current working directory must not be writable by group or other.
6. The command being executed cannot be a symbolic link.
7. The command being executed cannot be writable by group or other.
8. The command being executed cannot be a setuid or setgid program.
9. The target UID and GID must be a valid user and group on this system.
10. The target UID and GID to execute as, must match the UID and GID of the directory.
11. The target execution UID and GID must not be the privledged ID 0.
12. Group access list is set to NOGROUP and the command is executed.
13. php_value settings in .htaccess files should be removed. Values to be placed in php.ini file within script's main directory.

Now, most of them are not really telling me anything but what I found out was that if I get rid of the clean URLs and use ?q=/node/view/12 type of URLs instead then the site is back up, but that makes all of my previous URLs inaccessible obviously.

Here is what I did. I took everything out of the .htaccess file and replaced them with these entries:

Options +FollowSymLinks
RewriteEngine on
  RewriteRule ^(.*)$ index.php?q=$1 [L,QSA]

Now, I have my clean URLs back, but now my templates are all messed up somehow, and the site looks as if I have no template or the example template installed. See yourself at http://www.adsensed.com or http://www.powershotblog.com

In a weird way, when sometimes it loads the template however when you refresh the page you are back to no-template state. (This maybe a cache issue on my side though, I am not sure about it.)

If anyoe had a similar problem or anyone has an idea how to fix this problem I will really appreciate if you share it with me. This is not fun and I dont want to move all my sites to a new host at this point unless I cannot find a fix for this issue.

Regards

KC