Did I just say all my WordPress plugins seem to work fine with WordPress 2.1? It turns out one of the new features in WP2.1, where you can set any static page as the front page, will send your browser into a busy redirection loop, when you turn on Permalink Redirect plugin.
Well. The bug has been fixed now, and it is now 0.6.2. Go and download it if you are using WP2.1's new feature.
Thanks to Brian for pointing it out.