I think I'm hitting the same issue on an up-to-date installation of 10.10.

What I did, essentially, is:
  1. install emacs, org-mode, texlive-latex-base, texlive-latex-recommended
  2. create an org file with Cyrillic characters, in UTF-8
  3. request org-export to PDF

Here's what I'm getting for the very first cyrillic character, in the Shell interaction emacs buffer:

This is pdfTeX, Version 3.1415926-1.40.10 (TeX Live 2009/Debian)
 restricted \write18 enabled.
entering extended mode
(/home/deepfire/src/pyzzle/doc/documentation.tex
LaTeX2e <2009/09/24>
Babel <v3.8l> and hyphenation patterns for english, usenglishmax, dumylang, noh
yphenation, loaded.
(/usr/share/texmf-texlive/tex/latex/base/article.cls
Document Class: article 2007/10/19 v1.4h Standard LaTeX document class
(/usr/share/texmf-texlive/tex/latex/base/size11.clo))
(/usr/share/texmf-texlive/tex/latex/base/inputenc.sty
(/usr/share/texmf-texlive/tex/latex/base/utf8.def
(/usr/share/texmf-texlive/tex/latex/base/t1enc.dfu)
(/usr/share/texmf-texlive/tex/latex/base/ot1enc.dfu)
(/usr/share/texmf-texlive/tex/latex/base/omsenc.dfu)))
(/usr/share/texmf-texlive/tex/latex/base/fontenc.sty
(/usr/share/texmf-texlive/tex/latex/base/t1enc.def))
(/usr/share/texmf-texlive/tex/latex/graphics/graphicx.sty
(/usr/share/texmf-texlive/tex/latex/graphics/keyval.sty)
(/usr/share/texmf-texlive/tex/latex/graphics/graphics.sty
(/usr/share/texmf-texlive/tex/latex/graphics/trig.sty)
(/etc/texmf/tex/latex/config/graphics.cfg)
(/usr/share/texmf-texlive/tex/latex/pdftex-def/pdftex.def)))
(/usr/share/texmf-texlive/tex/latex/tools/longtable.sty)
(/usr/share/texmf-texlive/tex/latex/hyperref/hyperref.sty
(/usr/share/texmf-texlive/tex/generic/oberdiek/ifpdf.sty)
(/usr/share/texmf-texlive/tex/generic/oberdiek/ifvtex.sty)
(/usr/share/texmf-texlive/tex/generic/ifxetex/ifxetex.sty)
(/usr/share/texmf-texlive/tex/latex/oberdiek/hycolor.sty
(/usr/share/texmf-texlive/tex/latex/oberdiek/xcolor-patch.sty))
(/usr/share/texmf-texlive/tex/latex/hyperref/pd1enc.def)
(/usr/share/texmf-texlive/tex/generic/oberdiek/etexcmds.sty
(/usr/share/texmf-texlive/tex/generic/oberdiek/infwarerr.sty))
(/usr/share/texmf-texlive/tex/latex/latexconfig/hyperref.cfg)
(/usr/share/texmf-texlive/tex/latex/oberdiek/kvoptions.sty
(/usr/share/texmf-texlive/tex/generic/oberdiek/kvsetkeys.sty))
Implicit mode ON; LaTeX internals redefined
(/usr/share/texmf-texlive/tex/latex/ltxmisc/url.sty)
(/usr/share/texmf-texlive/tex/generic/oberdiek/bitset.sty
(/usr/share/texmf-texlive/tex/generic/oberdiek/intcalc.sty)
(/usr/share/texmf-texlive/tex/generic/oberdiek/bigintcalc.sty
(/usr/share/texmf-texlive/tex/generic/oberdiek/pdftexcmds.sty
(/usr/share/texmf-texlive/tex/generic/oberdiek/ifluatex.sty)
(/usr/share/texmf-texlive/tex/generic/oberdiek/ltxcmds.sty))))
(/usr/share/texmf-texlive/tex/generic/oberdiek/atbegshi.sty))
*hyperref using default driver hpdftex*
(/usr/share/texmf-texlive/tex/latex/hyperref/hpdftex.def) (./documentation.aux)
(/usr/share/texmf-texlive/tex/context/base/supp-pdf.mkii
[Loading MPS to PDF converter (version 2006.09.02).]
) (/usr/share/texmf-texlive/tex/latex/hyperref/nameref.sty
(/usr/share/texmf-texlive/tex/latex/oberdiek/refcount.sty))
(./documentation.out) (./documentation.out)

! Package inputenc Error: Unicode char \u8:Д not set up for use with LaTeX.

See the inputenc package documentation for explanation.
Type  H <return>  for immediate help.
 ...                                              
                                                  
l.17 
     

! Package inputenc Error: Unicode char \u8:о not set up for use with LaTeX.

... etc

That's what 'locale' says:
deepfire@wintermute:~$ locale
LANG=en_US.utf8
LC_CTYPE="en_US.utf8"
LC_NUMERIC="en_US.utf8"
LC_TIME="en_US.utf8"
LC_COLLATE="en_US.utf8"
LC_MONETARY="en_US.utf8"
LC_MESSAGES="en_US.utf8"
LC_PAPER="en_US.utf8"
LC_NAME="en_US.utf8"
LC_ADDRESS="en_US.utf8"
LC_TELEPHONE="en_US.utf8"
LC_MEASUREMENT="en_US.utf8"
LC_IDENTIFICATION="en_US.utf8"
LC_ALL=