Wordpress Multisite Hosting

Well, after several hours, I just found out that I cannot efficiently run Multisite on Mediatemple GS hosting, and I especially cannot use the Multi-DB plugin from your premium plugins. I am faced with a hosting change, and I was hoping for some suggestions. I would like to keep costs down, but still have a fairly good set of features and having certain root access is important, as well.

Please let me know what you think.