I was able to get the Type 1 versions working.  It seems that the problem the whole time was an orphan kpsewhich living in /usr/bin.  After removing it, TL2012's kpsewhich took over and everything is fine.

Troy