Execute Job With Stored Proc Signed with Certificate
I should have kept researching just a little bit longer.  I found this article and discovered I needed to counter-sign a few more stored procedures within msdb.  Once I did that my user was able to execute the proc, which kicked off the job.  

ADD COUNTER SIGNATURE TO sp_start_job BY CERTIFICATE ExecuteRestoreJobsCert
    WITH PASSWORD = 'password'
ADD COUNTER SIGNATURE TO sp_verify_job_identifiers BY CERTIFICATE ExecuteRestoreJobsCert
    WITH PASSWORD = 'password'
ADD COUNTER SIGNATURE TO sp_sqlagent_notify BY CERTIFICATE ExecuteRestoreJobsCert
    WITH PASSWORD = 'password'
go