Verification required
I did not have the same problem, but I also had to verify my payment details. I contacted Apple support about this problem.

They told me that I have to edit my Apple ID address via apple.com
I made a little change in my address and saved it. Than I restored my address like it was before. When I want to download an app now, it had no problem.

It could be that you need to verify your details once again after changing your address.

I'm not sure if this will solve your problem but for me it dit.