Bonjour! I took me hours to track this down but I finally can reproduce what I think to be a bug in kpsewhich.
After upgrading from teTeX 2.x to 3.x my *.tex-compiles got really slow, 3-5 minutes even for "latex sample2e". Strangely enough though the problem did only occur with my account, not with root's. So I created another "simple" user called test. Test was able to compile as fast as root. Therefore I assumed that some environment variables were not set for my account. That was the point: My $HOME env var was set to "/home/thomas/". Running "kpsewhich -show-path=tex" with this HOME-var took ages. Then I set $HOME to "/home/thomas" omitting the trailing slash. That made my compiles as fast as the others. This is reproducible on my system. I use teTeX 3.0 on Gentoo (tetex-3.0-r3). Hope this helps someone. Cheers, Thomas -- http://krapplack.de/