Is there any way to add next and previous category links to my category archives without resorting to php/perl/etc?  Essentially I want this:

<< Category Foo | Main | Category Bar >>

At the top of each category archive.  This is easy with the date based archives, but the MTArchivePrevious and MTArchiveNext tags (apparently) won't work.

Is there any way to do this?

No, I don't believe there's tags for this.  Yeah, you could surely do this with some php.  :)