I had that problem for a couple of days.
What fixed it for me was going into iTunes on my computer and re-entering my billing info (credit card number, cvv2, expiry).
The fields were previously filled and nothing had changed in the past year or so, but for whatever reason even putting the exact same data back in worked and I haven't seen that message since.
Hope it works for you too.