Os repositórios do Kubuntu são os mesmos do Ubuntu. Eu uso o Kubuntu aqui e não tenho problemas. E estou usando uma variedade muito grande de programas: de jogos até editores de vídeo.
Som, Áudio, Multimídia... tudo funciona perfeitamente.
O que aconteceu, na minha opinião, é que quando o KDE saiu da versão 3.5 e foi para a 4.0, ficou com muitos bugs. Ainda estava em fase experimental. Muita gente que usava o KDE sentiu uma mudança muito grande no padrão. Foi um susto mesmo! Isso levou vários usuários (eu inclusive) a abandonar o KDE e passar para o Gnome.
Com a correção dos bugs, o KDE, agora em sua versão 4.4.5, se tornou uma ferramente fantástica, tanto no aspecto visual quanto em performance. Claro, basta configurar. Eliminar efeitos visuais que não utiliza, etc.
Não acho a interface poluída, não. A área de notificação é bem simples, porém separada do restante do painel, dando um ar mais organizado. Os aplets e gadgets que não uso simplesmente eu apago, e pronto.
Aliás, você pode até colocar outro painel no topo, parecido com o gnome.
Em dois aspectos, KDE é imbatível:
1. Extrema facilidade para gerenciar mime types. Por exemplo, se você quiser que todos os arquivos do mesmo tipo abram com um determinado programa, é só usar o menu de propriedades do arquivo. Isso pode ser feito no gnome mas é mais complicado.
2. Possibilidade de abrir o terminal dentro da janela da própria pasta (a tecla de atalho é F4) no Dolphin. Não vejo nada parecido com isso no Nautilus.
Mas todos os dois sistemas são bons. Vai do gosto. Eu, porém, fico com o KDE (Kubuntu).