Movendo esse comentário para sua própria resposta, parece que seu /etc/apt/sources.list
está com defeito. Edite-o para remover a linha que contém a segurança debian e substitua-a por
deb http://ftp.nl.debian.org/debian/ lenny main contrib non-free
para a distribuição principal,
deb http://security.debian.org/ lenny/updates main contrib non-free
para atualizações de segurança e
deb http://volatile.debian.org/debian-volatile lenny/volatile main contrib non-free
Para as chamadas atualizações 'voláteis', execute apt-get update; apt-get -uf upgrade
para atualizar todo o seu sistema e tente instalar o php5-cgi novamente.
(ETA: Você pode substituir 'nl' pelo seu próprio código de país para obter servidores um pouco mais próximos de sua localização física e, esperamos, melhores velocidades de download)