He estado "googleando", y he llegado hasta
esta página en la que parecen haber resuelto un problema similar, y por lo visto la solución está en
este mensaje, y parece estar relacionada con el archivo /etc/apt/preferences (archivo que, por cierto, yo no tengo en mi Debian Lenny).
Dinos si tienes el archivo /etc/apt/preferences, y cuál es su contenido.