Thought this was odd. Happened to me too. Tried to change password via mobile but Google didn't like it. Managed to change it via desktop. Then logged in with new PW on mobile and Google message went away.
Maybe it has something to do with a recent Android update?