Tube ace is pretty rough. However, if you're sure you want to use it, any host should work fine. Make sure they have ffmpeg and GD available and you will be fine. Keep in mind that a lot of hosts aren't going to be cool with you encoding videos en masse on a shared account so look at either a VPS or a dedicated. For my cheap shared accounts and VPS I use
Amerinoc