Thanks to the amazing Apache guruishnocityness that is Nathan Dove, my tag URLs are now beautified.

For others who use Ultimate Tag Warrior as their WordPress tag plugin of choice but can’t seem to get the pretty URLs to work, the fix was actually relatively simple. Simply insert the following in wp-includes/classes.php, line 1542:

if (!preg_match("!^tag/!", $request_match) && (preg_match("!^$match!", $request_match, $matches) ||
preg_match("!^$match!", urldecode($request_match), $matches))) {

Thanks again to Nathan Dove for the fix, and Christine Davis for creating UTW in the first place. You rule!