7.10から8.04にアップデートした環境ですが，きちんと機能してるみたいです。

$ sudo apt-get install x[TAB][TAB]

のように，TABを2回押すと

Display all 1120 possibilities? (y or n)

と表示され，yにすると一覧が表示されます。

参照先のサイトにあるように，bash-completionをインストールする必要があるようですが，インストールされていますか？

ちなみに，家の環境ではbash-completionはすでにインストールされていて(特に意識して入れた記憶はありませんが)，ホームディレクトリに.bashrcもありました。