Mac Mail having problems connecting to gmail

I have used mac's mail program for years with my gmail account without a problem. In the last week it has randomly stopped connecting and the an hour or so later will work again.

There is an "!" next to my gmail account and when i click on it it says, "Unable to connect. There may be a problem with the mail server or network. Check the settings for account "gmail" or try again. The server error encountered was: Web login required (failure)"

I havent changed my password or setting with gmail recently. My iphone still gets the mail without a problem. And my other computer is having no problem either.

Any other suggestions?