App store updates won't download I changed my Apple ID password.

I can log successfully into my Apple account using my new password online.

I can download songs from iTunes using my new password.
But When I go into App Store, and select "Updates". I click on Update tab for App, I get prompted for my Apple ID Password. I enter my new password, click OK, the "UPDATE" tab flashes from "INSTALLING" back to "UPDATE". Update  does not complete! 

This happens on both my iPhone and iPad and I can't get past it. 

How can I fix this?
Did you try via the settings > iTunes and App Store? Click Apple ID and logout and back in.
Login again there, and that did the trick for me.

EDIT: My problem was solved when I removed iCloud from my iPad and iPhone and logged in with new credentials.