Error: The certificate cannot be dropped because one or more entities are either signed or encrypted using it
My bad.

I should be using

DROP COUNTER SIGNATURE FROM OBJECT::dbo.sp_sqlagent_notify BY CERTIFICATE certificate_name


instead of

DROP SIGNATURE FROM OBJECT::dbo.sp_sqlagent_notify BY certificate_name