Randomly mail says pop email username and password was incorrect

Switch to IMAP. POP doesn't handle multiple connections or dropped connections very well.

If it is random that means there is another email client also accessing the server; perhaps your computer is set to automatically fetch mail. When a POP3 server has an open session and receives another open request it closes the session and sends an "incorrect password" message to both clients. This is a holdover from the time connections were unreliable and lost connections while a session was open were common. So the message is misleading; all it means is that another session was not closed properly.

So what is the resolution? Does this mean that I can't/shouldn't leave gmail open the mac, if I want to reliably be able to retrieve mail from my phone...that doesn't seem to make sense, and is compounded by the fact that (barring someone having hacked my gmail), I can say that the other mail client, on my mac, is closed, and I am still having the same problem.

Thoughts?

There is a problem in your mail configuration, either in gmail settings or on your phone. You said the phone gmail account is set to IMAP; if it truly was IMAP this would not happen. Have you also gone into gmail settings from your browser and set the server mode to IMAP?