J’ai fini par résoudre mon problème assez facilement avec le paquet kernel-image… Il m’a suffit de désinstaller tous les paquets kernel-image de ma machine, même le paquet contenant le kernel courant, malgré les multiples alertes affichées à ce moment-là par apt. J’ai ensuite installé le kernel-image-2.6.8-3-686-smp que je voulais installer et ça a rebooté sans problème. Merci quand même à ceux qui ont tenté de m’aider !
C’est ce qui s’appelle travailler sans filet 
Je me suis rendu physiquement aux côtés de la machine pour l’occasion, et j’avais toujours un Live CD de Knoppix sous la main au cas où… 