Сначала проверьте, чтобы в вашем /etc/apt/sources.list помимо main и restricted были активны также ветки universe и multiverse.
Что бы установить кодеки для проигрывания mp3, mov (Quicktime), DVD, avi, Windows Media, и другие, а так же установить расширенный набор шрифтов нужно установить пакет kubuntu-restricted-extras командой:
sudo apt-get update && sudo apt-get install kubuntu-restricted-extras
При установке будет закачено порядка 35 Мб.
Не забудьте при установке Java принять лицензионное соглашение (поставить галочку) когда будет спрашивать.