"The first issue is that "./Build test" doesn't recursively go into the "t" directory. I have tests in "t/lib/*.t", and they do not get run with "./Build test"."

How sure are you that Module::Build has the capability of traversing test sub directories? I use ExtUtils::MakeMaker and I know for fact it does, because I wrote the tests and documentation for that functionality myself (see that here). Here's the t/ directory for one of my own distributions that have several sub-dirs in the t/ directory.