I get the same error as: Apt-get update on circlecI/classic - GPG error: Signature verification error
I’m using ubuntu-1604:201903-01. Is there any newer image? I can’t find anything in the docs 
Does the workaround from that post work?
wget -q -O - https://dl-ssl.google.com/linux/linux_signing_key.pub | sudo apt-key add -
JFYI, there were also other keys that start to fail.
The newly release image ubuntu-1604:202004-01 announced here, seems like it did the trick!
I find it very disappointing though that I had to wait for months just for an apt update…