Thanks for the reply. I ended up stumbling upon an apparent solution.
It seems that Google perhaps requires some sort of authentication after changing your password? I wasn't aware of this and never saw anything of the sort when logging in on my desktop. Upon downloading the GMail app and logging in there, however, I found that I was required to enter my password twice, the second time also confirming via CAPTCHA.
After that, I attempted to add my GMail account again, and voila! It works now. Very interesting indeed.
EDIT: I finally found this:
https://www.google.com/accounts/DisplayUnlockCaptcha