Codepoetry has a nice tip for Movable Type bloggers on how to change your archiving scheme without sapping your Google juice or 404ing everyone who’s ever linked to you. It involves creating a secondary archive URL (your old one) for every archive type you want to change, then setting up the template for that new archive to be a redirect to the revised URL.
The CP entry does a better job of explaining this than I do. The author opts for a meta refresh to redirect visitors, but I’d probably go with a PHP redirect if possible. It’s more elegant, in my opinion, and doesn’t force visitors to look at the intermediate page.