texdoc often fails for me, e.g.
$ locate beameruserguide.pdf
/usr/share/doc/latex-beamer/beameruserguide.pdf.gz
$ texdoc -l beamer
1 /usr/share/texmf-texlive/doc/latex/tdclock/tdclock-beamer-example.pdf
Please enter the number of the file to view, anything else to skip:
$ texdoc beameruserguide
Sorry, no documentation found for beameruserguide.
On the other hand this works:
$ texdoc -l tikz
1 /usr/share/texmf/doc/pgf/pgfmanual.pdf.gz
Thus, the questionable compressing of pdfs by the Ubuntu packages does not seem to be the reason.
(I am using Ubuntu 10.04)
Sure, I often use google to find LaTeX documentation, but sometimes net access is not available and often the current documentation contains some nice feature which are not available yet with the package versions installed on the local system.