John, What operating system are you using? If it is ubuntu linux, installing texlive- latex-extra and/or texlive-lang-greek through apt should do it (e.g. sudo apt-get install texlive-latex-extra). If it's Windows and MiKTeX, you might have to do it by hand. If you give more detailed information and perhaps a minimal example, it would be easier to give a better response.
By the way, I just tried what you described on my Windows XP computer with LyX 2.0.2 and MiKTeX 2.9. The .pdf compiles just fine. I think MiKTeX is grabbing the package for me automatically. Jacob
