環境は、Scientific Linux 6.2 (x86_64)。EL 6 系はどれも同じだと思います。

Apache を利用する場合、TypesConfig ディレクティブで OS の定義する MIME タイプ (/etc/mime.types) を読み込むように設定している場合が多いと思います (デフォルトなので、特に変えていなければそうなっているはずです)。
今回のサーバ移行で CentOS 5 -> Scientific Linux 6 に OS を変更したのですが、拡張子が *.pl のスクリプトに対する MIME タイプが変わっていたためハマりました。
CentOS 5 では *.pl ファイルに対する MIME タイプが未定義だったのに対して、SL 6 では application/x-perl という MIME タイプが割り振られています。

このため、*.pl の拡張子を持つ Perl CGI 内で明に MIME タイプ (Content-Type ヘッダ) を出力していない場合 (特に Location: のリダイレクトヘッダ出力時などは忘れがち)、text/plain ではなく application/x-perl が使われてしまいます。この現象による問題が顕在化するのが SoftBank のフィーチャーフォンで、こちらの blog で述べられているような問題 (アクセス不能) が発生してしまうようです。

対応策としては、やはり上記 blog で述べられているように、Content-Type を確実に出力するように改修する、がベストな所だと思います。

# ということで、メールにてご報告いただいた方、ありがとうございました。