Comment 2 for bug 249340

I just experienced the same. I came through a reboot doing this.

1.
Did a "sudo killall locale-gen" whenever that problem arose

2.
I watched closely when grub and the new kernel was installed.

3.
Checked that /boot/grub/menu.lst looked right

4.
Checked /lib/modules/2.6.24-19 looked right

5.
Had a good look at the report about failed packages, nothing alarming showed up

6.
Rebooted without a problem

7.
"sudo aptitude upgrade" which fixed the problems

8.
Have a fully functional desktop