13.10ですが、そのようなことは起きてませんね……。

popopopoonさん、kitajuさん、レスありがとうございます。

Lubuntu では
/etc/apt/sources.list
を「ソフトウェアとアップデート」（Ubuntu の「ソフトウェアソース」に相当）で開いてみると
main,universe
のみにチェックが入っている状況ですが、
texlive-lamg-cjk がインストールされております。

今回、チェックのために
Ubuntu 12.04 LTS を新規インストールしてみました。
しかし、
/etc/apt/sources.list
を「ソフトウェアソース」で開いて
「Ubuntu のソフトウェア」は
main,universe,restricted,multiverse
（texlive-lamg-cjk は universe のパッケージのようですので、こうする意味はないでしょうが）
の全てにチェックして
「他のソフトウェア」も全てにチェックしてから
$ sudo apt-get update
を実行した後に、
Synaptic で texlive-lang-cjk と入力してもパッケージが表示されない、
という訳の分からない状況になっております。
texlive と入力した場合は様々なパッケージが表示されますので、
Synaptic が壊れているわけではありません。
LinuxMint13 においても同じ状況です。

ちなみに、Ubuntu の /etc/apt/sources.list を
gedit で開いた内容も念のために貼り付けておきます。

# See http://help.ubuntu.com/community/UpgradeNotes for how to upgrade to

# newer versions of the distribution.
deb http://jp.archive.ubuntu.com/ubuntu/ precise main restricted multiverse
deb-src http://jp.archive.ubuntu.com/ubuntu/ precise main restricted multiverse

## Major bug fix updates produced after the final release of the
## distribution.
deb http://jp.archive.ubuntu.com/ubuntu/ precise-updates main restricted multiverse
deb-src http://jp.archive.ubuntu.com/ubuntu/ precise-updates main restricted multiverse

## N.B. software from this repository is ENTIRELY UNSUPPORTED by the Ubuntu
## team. Also, please note that software in universe WILL NOT receive any
## review or updates from the Ubuntu security team.
deb http://jp.archive.ubuntu.com/ubuntu/ precise universe
deb-src http://jp.archive.ubuntu.com/ubuntu/ precise universe
deb http://jp.archive.ubuntu.com/ubuntu/ precise-updates universe
deb-src http://jp.archive.ubuntu.com/ubuntu/ precise-updates universe

## N.B. software from this repository is ENTIRELY UNSUPPORTED by the Ubuntu
## team, and may not be under a free licence. Please satisfy yourself as to
## your rights to use the software. Also, please note that software in
## multiverse WILL NOT receive any review or updates from the Ubuntu
## security team.

## N.B. software from this repository may not have been tested as
## extensively as that contained in the main release, although it includes
## newer versions of some applications which may provide useful features.
## Also, please note that software in backports WILL NOT receive any review
## or updates from the Ubuntu security team.

deb http://security.ubuntu.com/ubuntu precise-security main restricted multiverse
deb-src http://security.ubuntu.com/ubuntu precise-security main restricted multiverse
deb http://security.ubuntu.com/ubuntu precise-security universe
deb-src http://security.ubuntu.com/ubuntu precise-security universe

## Uncomment the following two lines to add software from Canonical's
## 'partner' repository.
## This software is not part of Ubuntu, but is offered by Canonical and the
## respective vendors as a service to Ubuntu users.
deb http://archive.canonical.com/ubuntu precise partner
deb-src http://archive.canonical.com/ubuntu precise partner

## Uncomment the following two lines to add software from Ubuntu's
## 'extras' repository.
## This software is not part of Ubuntu, but is offered by third-party
## developers who want to ship their latest software.
deb http://extras.ubuntu.com/ubuntu precise main

texlive-backportsというPPAを導入すれば12.04でも使えるはずですよ。

例えばこんな記事。
http://xr0038tech.hatenadiary.jp/entry/20130326/1364308990