Regex help needed for complicated mass renaming

From: BBQ (bbq_pit_at_hotmail.com)
Date: 02/28/04 

Date: 28 Feb 2004 10:18:56 -0800

I have inherited a series of files in the following format:

TestTest1.txt
TestTest2.jpg
Test_Test3.txt
Test_TestTest4.txt
NASATest.txt
NASATest5.txt
TestTestTestTest.mpg
Test6Test.txt
Test.txt

which I want to rename as follows:

test_test1.txt
test_test2.jpg
test_test3.txt
test_test_test4.txt
nasa_test.txt
nasa_test5.txt
test_test_test_test.mpg
test6_test.txt
test.txt

In other words: everything lower case (this bit I can do) and
underscores before each uppercase letter (as long as it is not the
first character).

I've been trying (and failing) to put a '_' before every captial
letter, I was then going to chop of the first character if it is a '_'
(which I can do) and then lower case everything (which I can do). As
for not inserting multiple '_'s in between multiple capitials in a row
(NASATest.txt -> nasa_test.txt), I'm not sure where to start. I was
going to just alter those by hand.

Better solutions are most welcome (and if they are quite cryptic, a
few comments also would be great).