Monthly archive per category

I’m using a custom permalink /%category%/%postname%/ with per /%category%/ page an overview of the posts in that category. I’d like to have my archive also per category and per month. Something like the month overview like here (http://www.writteninmusic.com/archive/), but then per category.

I’ve tried this plugin (http://snipplr.com/view.php?codeview&id=17432) and that kind of works, but ruins all the permalinks…

Has somebody some good ideas how to do this or even build a more advanced archive?

Thanks in advance!
Jorim