Estranho. O kate está nos repositórios.
No synaptic, vai em Configurações>Repositórios
Na aba "Programas do Ubuntu" certifique-se que todos estão marcados (Onde tem "Disponível pela Internet"). Clica em fechar e depois em recarregar.
Feito isso, faça uma busca novamente por "kate".
