この現象に悩まされる人がけっこう多いみたいですよ。
対処法として下記の方法があるようです。
設定アプリ〉〉一般〉〉日付と時刻の中の「自動設定」を「オフ」にします。これだけで直る人もいるようです。
iOS6アップデート不具合!App Storeに接続できないときは | AppWoman
駄目な場合は日付をさらに操作します。現在時刻を「2年後」ぐらいに設定〉〉App Store起動〉〉アップデートタブをタップすると接続エラーになりますので、一旦App Storeを終了します(バックグラウンドからも終了させてください)。再度、一般〉〉日付と時刻から自動設定を「オン」にすると、直る確率が高いようです。
その他に、「WiFi環境でApp Storeに接続すると改善される」「しばらく放置」などもあるようですよ。