tromey: i don't think depending on some language is particulary troublesome. if worse comes to worse you can always bundle and statically compile the build tool (if you move to python as the implementation and tool language, you could see it as reducing the dependencies...granted you're requiring a less common one...). you also have a known entity instead of having to pander to the lowest common denominator.
(in this respect it might be to your advantage to explicitly say on the front end 'our build tool uses python and takes advantage of these features: <exact-list>. if you are building a python work-alike for the purposes of running our tool it must support at least this subset to be successful.' this approach lets you take an open-format approach in which you aren't requiring any specific implementation of a language, only a set of features and syntax.
you end up pretty much with a language spec for python-lite, but it allows you, if need be, to go off and code your own implementation of it without worrying about doing all of python for it to work. just saying you need language X doesn't give you enough information; it would be like saying 'this program requires a computer.' on the other hand if you tell people you need computer A, with processor B, OS C, libc D, etc, and spec the whole thing out, people will have no misunderstandings about whether or not what they have will be successful in running the program.
as tedious as specifying exactly what subset of functionaly you use is and then specifying exactly what that functionality means, i think it might save some issues in the long run as python might mean something else in a few years. ).
the particular issues i can think of have to do with the language being out of one's control. what happens if python 3 turns into something you no longer want to use? do you fork it? another issue is that i feel that gmake, m4, and sh are more or less stable (could be wrong here) from the standpoint of the end-user. that is, there isn't going to be some new feature added that breaks your existing stuff.
no matter what you'll get a lot of whining. everyone will be annoyed with something...because they liked auto*, LANG=(python|perl|lisp|arc|scheme) is too wierd and they can't understand it, you're depending on $LANG (nevermind the duct tape we already depend on), etc, etc. i suggest you let these people sod off.
are you aiming to replace just automake, all of auto*? or auto*, and its little make(1) too?