Siguiendo el HowTo, es lineal. No debería haber manera de que fallara ;-D
"libgd2-noxpm-dev - GD Graphics Library version 2 (development version)" <- Si existe ;-)
Debes tener un poco chunguillo el sistema de paquetes. Quizás tienes entradas en sources.list de Sarge y otras de Sid? Si es así, ponlas TODAS de Sid (no las pongas de Sarge, ya es demasiado tarde, porque tendras algunos paquetes de Sid instalados ya).
Busca un buen sources.list porque el problema debe venir de ahi. SI lo necesitas, te posteo el mio.
Ah, y sigue el HowTo al pie de la letra ;-P Lee las notas tb, puede que ahí ponga algo que se te aplica a tí.
Si no recuerdo mal, el howto te había ido hasta ahora, así que no hay motivo por el que ahora no debería irte ...
Ya diras algo.
Un saludo!