BUFFALOの無線LANルーター経由でネットに繋いでいる場合、こいつが邪魔をしてるみたいです。 ルーターを最新版にアップデートしたら何のことはなくiPhone用のソフトウェアがダウンロードできました。

iTunesにバックアップとる。念のため「データお預かり」にもアドレス帳を保存 →プロファイルを削除 →復元 →メール初期化（プロファイルを再びインストール） というめんどくさい作業で治りました。ご参考まで。