I'm assuming you've carefully checked to be sure they match up perfectly, including the case.
Some Android keyboards have a habit of adding a space at the end of the username before you move on to the password box -look for this and backspace to get rid of it if it's there.
Otherwise, using your computer that has no trouble logging into your mail account, go to settings and change your password.