I searched the error for a while and saw a lot of things about certificates differing between msdb and master. But I checked the certificates and they were identical.

I compared my server to others, and noticed that the ##MS_AgentSigningCertificate## user was missing from the master database. Running the following query worked for me:

USE MASTER

CREATE USER [##MS_AgentSigningCertificate##] FOR LOGIN [##MS_AgentSigningCertificate##]

GO

GRANT EXECUTE TO [##MS_AgentSigningCertificate##]

go