Investigating further I realized that it was not being authenticated because the server time did not match the time of the service's JWT Token generation.

ERROR: (gcloud.auth.activate-service-account) There was a problem refreshing auth tokens for account xxxxxxx: ('invalid_grant: Invalid JWT: Token must be a short-lived token (60 minutes) and in a reasonable timeframe. Check your iat and exp values in the JWT claim.', {'error': 'invalid_grant', 'error_description': 'Invalid JWT: Token must be a short-lived token (60 minutes) and in a reasonable timeframe. Check your iat and exp values in the JWT claim.'})

I'm not sure why he only started complaining now, but I adjusted the server's time zone and it started working again.