Webサーバにベリサインが用意している中間認証局証明書が正しく導入されているか確認されては如何でしょうか。

Q：中間CA証明書のインストールについて
https://www.verisign.co.jp/ssl/help/faq/110089/index.html

> 日本ベリサインでは、2009年5月18日に認証局証明書の変更を行いました。更新取得されたサーバIDをインストール する場合も、必ず以下より新しい中間CA証明書を入手のうえ、ウェブサーバにインストールしてください。

と有ります。
あくまでも想像ですが、この中間認証局証明書を介してPCと携帯電話で別々のルート認証局に検証パスが通るような仕組みになっていた場合、PCでは正しく証明書階層が繋がるが、携帯では繋がらないという事が起こる「かも」しれません。


なお本件とは直接関係が無いと思いますが、2048bit鍵への対応ではベリサインはそのような方法で対応する模様です。

4. 証明書製品の仕様変更の内容について
(イ) セキュア・サーバID
https://www.verisign.co.jp/ssl/about/20100128b.html

ベリサインのセキュアサーバIDでは鍵長の2048bit化に際して、1024bit鍵を使った既存のルート認証局への検証パスを確保するため、既存ルート認証局から「VeriSign Class 3 Public Primary Certification Authority - G5」(以下中間CA-G5)という名で中間認証局証明書を発行します。この中間認証局から「VeriSign Class 3 Secure Server CA - G3」(以下中間CA-G3)という別の中間認証局証明書が発行され、さらにこの中間認証局から目的のサーバ証明書が発行される形となるとの事です。

「VeriSign Class 3 Public Primary Certification Authority - G5」(以下ルートCA-G5)は、PC用のブラウザでは「信頼される認証局」として予め組み込まれていますので、2048bit鍵を使ったサーバ証明書をPCで観た場合には、

サーバ証明書→中間CA-G3→ルートCA-G5

となりますが、携帯電話で観た場合には、

サーバ証明書→中間CA-G3→中間CA-G5→既存ルートCA

というパスを通る事になります。ここで中間CA-G5の導入をしていなければPCではエラーにならないが携帯ではエラーになるという、今回と同じような現象になるものと思われます。