Recently, I had noticed lots of 404 error generated by my wordpress software. My old wordpress tag structure changed from:
/tips/tag/linux_software
/tips/tag/one_two_foo

To:
/tips/tag/linux-software
/tips/tag/one-two-foo

As a result lots of error 404 was dumped into my log file. I wrote a small php code to get rid of the problem:

My tag301.php:

<?php
$newTagUrl='http://www.cyberciti.biz/tips/tag/'.str_replace('_', '-', $_GET['r']);
@include_once("../include.genlib.php");
movePage(301, $newTagUrl);
?>

Finally, I updated my mod_rewrite (lighttpd rewrite engine) to redirect to new location:

 "^/tips/tag/(.*_.*)+$" => "/tag301.php?r=$1"

Code for movePage() is here.