As soon as I start my computer this message appears:
Applications can no longer access your ...@gmail.com Online Account
Choose Online Accounts from the user menu to reinstate access to this account.
So I open Online Accounts, enter the password and it gets connected.
But when I restart the computer, the same message comes up. I have repeated the process three times but no use.
If you turn off the "Access your Google Calendar" option under Evolution Data Server the account will stay authorised after you restart your computer. Admittedly this solution isn't ideal especially if you use google calendar but it at least partly fixes the problem and removes the need to reauthorised on every restart.
And press again "Grant access" if comes to the top-bar. Changing only the option is not enough, which it asks at least with 2-step authentication.
Some things you can Try.
remove the account from Ubuntu and login to your Google account in a browser and go to the settings page for your account click security-> then below you should see "account permissions" and remove anything from Ubuntu.
After that try to add the account again.
I had the same problem in Ubuntu 16.04 LTS.
The way I solved it was to go to System Settings --> Online accounts and then turn-on the button on top right to grant access:
