GNU Emacs Gnus can't connect to gmail IMAP

Question

I'm in the process of configuring Gnus to retrieve emails from my gmail account via IMAP. I have done as recommended at https://www.emacswiki.org/emacs/GnusGmail, however I keep on getting errors from Gnus upon startup:

Opening connection to imap.gmail.com via tls...
nnimap (gmail) open error: 'NO (ALERT) Please log in via your web browser:
https://support.google.com/mail/accounts/answer/78754 (Failure)'.  Continue? (y
or n)  y
Saving file /home/mark/.newsrc-dribble...
Wrote /home/mark/.newsrc-dribble [2 times]
Gnus auto-save file exists.  Do you want to read it? (y or n)  y
Opening nnimap server on gmail...
Server nnimap+gmail previously determined to be down; not retrying
Opening nnimap server on gmail...failed: NO (ALERT) Please log in via your web
browser: https://support.google.com/mail/accounts/answer/78754 (Failure)
Checking new news...
Reading active file from gmail via nnimap...
Opening nnimap server on gmail...
Server nnimap+gmail previously determined to be down; not retrying
Opening nnimap server on gmail...failed: NO (ALERT) Please log in via your web
browser: https://support.google.com/mail/accounts/answer/78754 (Failure)
Reading active file via nndraft...done
Checking new news...done
No news is good news
Warning: Opening nnimap server on gmail...failed: NO (ALERT) Please log in via
your web browser: https://support.google.com/mail/accounts/answer/78754
(Failure); Server nnimap+gmail previously determined to be down; not retry\
ing; Opening nnimap server on gmail...failed: NO (ALERT) Please log in via your
web browser: https://support.google.com/mail/accounts/answer/78754 (Failure);
Server nnimap+gmail previously determined to be down; not retrying
gnus-group-read-group: No group on current line

I have GnuTLS installed and gnutls-cli seems to work with imap.gmail.com:993, I'm getting "OK Gimap ready for requests".

Here's my ~/.gnus:

;;
(setq gnus-select-method
      '(nnimap "gmail"
          (nnimap-address "imap.gmail.com")
          (nnimap-server-port 993)
          (nnimap-stream ssl)
          (nnir-search-engine imap)
          (nnimap-authinfo-file "~/.authinfo")))

(setq smtpmail-smtp-service 587
      gnus-ignored-newsgroups "^to\\.\\|^[0-9. ]+\\( \\|$\\)\\|^[\"]\"[#'()]")

My ~/.authinfo looks like this:

machine imap.gmail.com login [e-mail] password my_password port 993
machine smtp.gmail.com login [e-mail] password my_password port 587

What could be the problem?