Pode soar um pouco simples demais, mas muitas vezes me encontro nessa situação, para descobrir que na verdade eu o tenho instalado, mas não está carregado ou em execução no momento. Outras vezes, tendo uma carga de serviços em alguns sistemas, não vejo isso na lista porque em alguns casos é nomeado de forma diferente (mas a palavra Tomcat está nela, de alguma forma). De qualquer forma, se você continuar tendo problemas, no Bitnami.org existe um instalador para o Tomcat, isso pode facilitar as coisas.