Me han comentado que eApps.com da un buen servicio, aunque sus precios son "de gama alta":
http://www.eapps.com/ManagedHosting/...aredPrices.jsp
De todas formas, siempre puedes buscar "tomcat hosting" en google y encontrarás un montón de ellos.
Un saludo