"I did it on kubuntu jaunty, but it could work almost the same if you tried on debian or any other distribution that has a package manager (or even without it, thought the steps will change, of course).
"First thing, I booted the box with a Kubuntu LiveCD. After having booted, I mounted the root partition of my busted GNU/Linux:"