Você precisa adicionar o componente universe a qualquer uma das fontes "principais" (não de segurança).
deb http://us.archive.ubuntu.com/ubuntu/ karmic main restricted universe
deb-src http://us.archive.ubuntu.com/ubuntu/ karmic main restricted universe
Pacotes que não estão no componente main são marcados como tal com um rótulo vermelho após seu nome no banco de dados de pacotes do Ubuntu: link