情報だけですが設定じゃないかな？
Ubuntu 10.10   Nautilus 2.32.0  の環境でウィンドをアクティブにしてキー入力をするとウィンドウ右下にフローティングっぽいウィンドウに短い一行テキストが表示されて入力の文字（半角英数）に反応して確答するフォルダにフォーカスが移ります。

これが8.04の頃の動作と同じかどうかは分かりませんが、類似の機能は有る用です。

che による投稿:

それが、 Nautilusのウインドウで英数キーを押しても、フローティングウインドウも表示されなないし、全く反応ないのです。

これが何を意味しているか分かりませんが、「日本語キーボード」の[英数/CapsLock]キーなら押しても何も変化しません。
検索可能な文字キーを入力すれば、入力ウインドウが現れてキーを入れるごとに指示するファイルが変化します。もし日本語ファイルを検索する場合、入力ウインドウを出すために、何かの文字を入れて入力ウインドウを出し、それから、その文字を消す操作が必要です。ですから、日本語ファイルを探すときには、[Ctrl+F]で検索してしまったほうが簡単です。

その後Ubuntu 11.04にアップグレードしてみましたが、状況は変わりませんでした。
そこでUbuntu 11.04を新規インストールしたところ、問題が解決しました。

新規インストールで解決したと言えるか疑問ですが、とりあえず問題はなくなりました。

以上報告いたします。