It would help if you posted your error message.
One thing just in general that gmail is doing is randomly blocking programs from using gmail via regular login, since they decided OAuth is more secure. Of course, they lie about the error message (claiming an inaccurate username/password combo) and then use scare tactics to try to stop you from switching the setting...
I'd provide a link to the previous person who had this problem with calibre, but I typed this on my Kindle Touch.
And without the error essage I cannot be sure that is the problem.