A página de instalação do Kivy dá uma dica:
sudo add-apt-repository ppa:thopiekar/pygame
sudo apt-get update
Eu usei o gerenciador de pacotes Synaptic para essa finalidade, dessa forma eu pude ver diretamente se o python3-pygame está disponível ou não, mas o comando terminal também fará o trabalho. Tudo executado com sucesso no Ubuntu 14.04.
Vamos para o python3.
Razão: pygames só é enviado em uma versão para o python 2 com o Ubuntu neste momento. Existem algumas páginas descrevendo como criar uma versão python3 você mesmo (para os usuários alemães acima: link ), mas obviamente isso é um pouco tedioso.