A todo el mundo en algún momento le han hecho falta librerías para poder usar/compilar algún programa. Buscarlas a veces puede ser un dolor de cabeza.
La mejor forma de hacerlo en Ubuntu (o mejor dicho en Debian) es buscar directamente en el sitio de la distribución.
Para buscarlas hay que meterse aquí:
http://www.debian.org/distrib/packages. Luego en bajar en la página y
Buscar en el Contenido de los Paquetes, ahi debe aparecer el paquete que incluye la librería que se necesita. Descargarla y voila!
// Gracias José