I have it now fixed. It looks like the most recent update to Android, or some similar event, changed the time settings on my phone. It was showing the correct time, but the underlying settings caused the problem. It was saying the time zone was set manually - I changed it to take the correct time straight from my mobile provider's network, and now 2FA is working again.
I'm letting people know about this fix, partly because Coinbase are notorious for taking weeks or even months to respond to support requests. I hope it helps (certainly I was getting a bit panicky!).
(Mods, if this is posted in the wrong place, please move appropriately).
I have kept my Samsung J5 2016 not updated because of the fear that I will lose all of my 2FA codes to different logins I use online. Can you confirm that after you updated Android the Google Authenticator app was untouched ? I am asking as when I moved/transferred all the data from my old Samsung to this one, the google authenticator showed up but empty, all my logins were not shown. I manually created them again from my old phone.