sempre da Synaptic, prova a disinstallare e poi reinstallare il kernel che non funziona: sono due voci, headers e images. Poi lo reinstalli e vedi se va bene.
Puoi anche installare, al posto del "generic" quello per "386", se hai un processore a 32 bit.
Io ho fatto una cosa simile reinstallando il kernel che non funzionava.