Ubuntu Package Searchで見たところでは、Hardyのperlは5.8.8のようです。
http://packages.ubuntu.com/hardy/perl/perl
そちらのperlはどのようにして導入したものでしょうか。自前ビルドならReadme.txt的なものが付属していたはずなので、それらのドキュメント類をあたれば、なにか判るのではないかと思います。
また、5.10に拘りが無いのであれば、5.8.8用のlibthreadsはあるようです。
http://packages.ubuntu.com/ja/hardy/libthreads-shared-perl

5.10系でなければならない理由がある場合で、かつ、Hardyである必要が無い場合はもうすぐリリースされる予定のLucidに移行するのが簡単かと思います。
perl関連は特に自分で追加したものは無いと思いますが、Lucid beta(RC?)環境で、

$ perl -e 'use threads; print "hello, world\n";'
hello, world
$ perl -v

This is perl, v5.10.1 (*) built for x86_64-linux-gnu-thread-multi
(後略)

となりました。

Hardyな環境がすぐには作れないので、取り急ぎ。
端末を開いて、
$ apt-cache search perl
$ apt-cache policy perl
あたりの結果を見て、backportsなどからインストールされたものであることが確認されれば、
$ sudo apt-get remove perl
などしてから、backportsを外して、
$ sudo apt-get update
$ sudo apt-get install perl
などとなるかと思います。
もしかしたら別途、
$ sudo apt-get install libthreads-shared-perl
などとしないといけないかも。

ああ、そうか。依存関係でいろいろ一緒に消されてしまうのですね。。

宛　awaseさん
間に合っていますでしょうか。もし、既に大変なことになっていたら、申し訳ありません。。

宛　Templerさん
ご指摘多謝です。

よかった。。

さて本題に戻りますが、Ubuntu提供の5.10.0はthreadsが使えるはずだったと記憶しています。
最初の投稿で、perl -vの結果に5.10.1と出たとありますので、なにか違うものを呼び出してしまっているようです。
which perl
してどこのperlを呼び出しているのか確認してみて下さい。
もしこれが/usr/bin/perlであれば、なにかの際に上書きしてしまったのかも知れません。
もし違うところのものであれば、/usr/bin/perlで実行してthreadsが使えないか確認してみて下さい。

「/usr/local/bin/perl」ということはコンパイルしてインストールしたのではないかと思えますので、思い出せましたら正規の方法でuninstallしてください。
それまでは、端末で「sudo mv /usr/local/bin/perl /usr/local/bin/perl.orig」としてリネームしておいた方が良いと思います。システムに不具合を引き起こす可能性もありえますので（今だけでなく将来的にも）。