Did they flat-out refuse to update their media server, or are they doing it at a later date? It seems unlikely to me that they'd risk compatibility issues for any reason. You could also try their VPS packages, where you can update it yourself.
If you wish to move to a new hosting provider, I recommend Terabyte Hosting Solutions, which is run by DosDawg here at Unity. Their servers are customized solely for Dolphin and their plans also come with media server service included. I'm not sure if they're offering the new media server version right now, but if not, they should soon.
Edit: I've moved this topic to the hosting forums.
BoonEx Certified Host: Zarconia.net - Fully Supported Shared and Dedicated for Dolphin