Eu estou no OpenBSD agora, então meu conhecimento específico do Ubuntu pode estar um pouco errado, mas você pode fazer o que eu fiz (eu também sou um convertido do Colemak) para o Ubuntu.
Para o console, adicione
loadkeys colemak
(ou pode ser)
loadkeys linux_console/colemak.iso15.kmap
para /etc/init.d/local
Consulte o RcLocal Howto para configurar o rc.local para o Ubuntu e a página do Linux / Unix do Colemak para informações adicionais sobre a configuração do console e do Xorg.
Você pode definir o Layout do Colemak a partir do GDM (na parte inferior) e do Sistema / Preferências / Teclado quando estiver logado