Se o conjunto de caracteres (encoding) de uma fonte não provê acesso direto a caracteres acentuados, (como é o caso do OT1, padrão do LaTeX) então o TeX gera estes caracteres sobrepondo o caracter base mais o acento. O algoritmo de hifenização, contudo, não hifeniza palavras formadas dessa forma.
Se uma fonte já provê acesso direto a caracteres acentuados, como as de codificação T1, estes caracteres são usados diretamente sem prejuízo do algoritmo de hifenização. O uso de encoding T1 é fundamental para a correta hifenização em Português.
Note que trata-se da mesma fonte, por falta a Computer Modern, apenas o que muda é o seu encoding, isto é, a ordem/disponibilidade dos caracteres dentro da mesma. Para selecionar estas fontes, inclua no preâmbulo do seu documento o comando
\usepackage[T1]{fontenc}
O antigo pacote t1enc não deve mais ser usado e existe hoje apenas por questões de compatibilidade com documentos antigos. O fontenc é mais atual, continua a ser mantido e é de uso mais geral, portanto preferível.