Ubuntu Hardy Update Freezes during "Generating locales..."

I was upgrading a Ubuntu machine at work yesterday, it froze while it set up the locales:

Setting up locales (2.7.9-4) ...
Generating locales...
en_AU.UTF-8...

(you can go for a coffee now, like, taking a shower and drive down to the town to buy it from Starbucks)

I killed dpkg and restarted the set up but it didn't help. More errors while after packages were being set up:

perl: warning: Setting locale failed.

I didn't get a good response from the #ubuntu channel but some Googling got me to bump into this forum topic. There are a number of solutions being suggested in the topic, what worked for me was by booting into the recovery mode to run the package manager again.

- yc