I've written up a quickie guide to adding the list of categories back to the sidebar in WordPress 2.5.1. This should work in WordPress 2.5, but I didn't test it there. This is only for 2.5.1, and its a hack, not a plugin. Its on my site, with screenshots:
I hope it helps and I hope someone who can actually code in PHP will write a plugin to make this happen.