On my new Ubuntu Netbook Remix 9.04 install, I installed the texlive-latex-base package to run the common LaTeX stuff. However, when I tried to compile a document with \usepackage{hyperref}, it failed saying that kvoptions.sty was not found.
For this, install the texlive-latex-recommended package. It’s all over Google, and I decided to add to it. (Besides, I haven’t posted in a while…)
Rikipedia 