結論から言うと 3 のケースがいっちゃんだるい。
1. モジュールのパス通してるか
このケースの典型エラーメッセージ
Can't locate Foo/Bar.pm in @INC
（※ 後述するがパスを通してない以外の原因でもこのメッセージが出ることがある）
対処法
use lib 'モジュールを置いてる Dir'; のしわすれてると思われる。ので、する。
use lib ってなんぞ？ とか @INC がわからない場合はここを読むいいでしょう。
モジュールの検索パスを調べる @INC - サンプルコードによるPerl入門
さらに詳しい解説がほしいばあいは perldoc -v @INC するもよし、あるいはほとんどのPerl入門書に解説が書いてるのでそれを読むもよし。
2. モジュールの最後で 1; してるか
このケースの典型エラーメッセージ
Foo/Bar.pm did not return a true value at ...
対処法
モジュールの最後で 1; する。（真を返す値ならなんでもいいけど）
3. パッケージ名の Typo
まともなエラーが出ない場合があるから一番めんどくさい
チェックポイント
a. そのモジュールを使うスクリプトのなかで正しい名前で use してるか
b. そのモジュールのディレクトリとファイル名が合ってるか（Foo::Bar というモジュールなら Foo/Bar.pm という名前が合ってるか）
c. そのモジュール内の パッケージ宣言で記述した名前があってるか（Foo/Bar.pm 内で package Foo::Bar; と確かに正しく書かれているか）
a と b は Can't locate ... とエラーが出て死ぬからまだ気づきやすいんだけど、b のケースは ロードまでは成功してしまう（メソッドを呼ぼうとした時点で突然の死を迎える） から一番厄介。
逆に言うと、ロードは成功してるのに メソッドの呼び出し で「そんなメソッドねーよ！」と怒られて死ぬ（確かに定義してるのに！）場合は、 c のケースを疑うと良い でしょう。