There have been a few buggy LaTeX packages around. I had the same problem. I found that by explicitly defining the variables below everything would work ok. I understand this shouldn't be necessary, but for some reason kpathsea doesn't do its job right on my system (by the way, you could try and set the varibale KPATHSEA_DEBUG=1/2/4/8/16/32 -- read the info file through emacs-- this will show a bunch of info about where kpathsea is looking for the various files and more. This is what lead me to explicitly set the variables below).
Good luck, Giuseppe # TeX, LaTeX etc. TEXMF=/usr/lib/texmf TEXMFLOC=/usr/local/lib/texmf TEXMFUSR=$HOME/texmf TEXINPUTS=.:$TEXMFUSR//:$TEXMFLOC/tex//:$TEXMF/tex// export TEXINPUTS