ほとんど bash しか触っていなかったので、インストールすれば 補完が効くものばかりと思っていました。
zsh の場合 apt-get した直後だと補完が効きません。
% rehash
上記コマンドを入力し、ハッシュテーブルを再構築することで大丈夫のようです。
UNIXの部屋 検索: rehash のサイトを見たのですが、 sh,bash は PATH を毎回探索するんですね。どうりで補完が効くわけです。