301 redirection when permalink change

Hello!
when I started my wpmu network I was a newbie so I left the permalink structure on default. Now I would like to change to improve seo and have nicer url, but off course I want to prevent 404 error for page/post already indexed with old url structure . I need a 301 system!

what I would like is
Post /%postname%/
Categories /%category%/%postname%/

In this (very cool) article about seo http://yoast.com/wordpress-seo-url-permalink/
they say I can add a simple code line to .htaccess
(RedirectMatch 301 /\d{4}/\d{2}/\d{2}/(.*) http://example.com/$1)
but I don't know if it'll works on multisite.

Another solution could be using one of the many plugin aviable.
Especially http://wordpress.org/extend/plugins/redirection/ that promise to "Automatically add a 301 redirection when a post's URL changes".
That solution can solve my problem easily , but can I be sure it works properly once set up to all my blog's post automatically and don't generate 404 at all?