結論

yum install texlive

だとtexlive2007とかいうのが入りやがる*1ので、texlive2010の最新版っぽいものを公式サイトっぽいところに行って解凍してインストーラぱなしたらそれだけでうまくいきました(リモートでインストーラ動かして研究室で動かしたらうまくいった)。
ちなみにFedora13とか14とかだと上記のyumで2010が入ってイチコロみたいです。
2010より前(2007, 2008, 2009)の時代の情報がいっぱい出てきてtexliveのインストールDVDマウントしてptexliveだのなんだのとかいろいろはすべて気のせいでした。唯一最後にハマったのはどっかで見たUTF-8に対応しておらず、EUCで書かないとダメという情報を思い出して丁寧にnkf(なんか入ってなかったのでyumでインストール)で変換したら盛大に文字化けし、どっかの質問箱でまったく同様の人がいて、「ログを見てください。UTF-8って書いてあるので合わせてください。」って指摘されてたのでわろしゅ。

platex --help
...
-kanji=STRING  set Japanese encoding (STRING=euc|jis|sjis|utf8)
...

普通にUTF-8対応してるし、デフォルトもUTF-8でした。
結局のところ、texlive2010からptex(※pナントカ…tex日本語版の何か)が入ってそれ入れるだけでOKということみたいです。フォントとか用意したり設定したりしないといけないかと思ったけど別にそんなこともなかった。

*1:ところでこれすでにメンテナンス対象外っぽいFedora12なんですけd