"'EXECUTE AS USER' failed" in SQL Server Agent job

Apparently the problem was that the new database was created with a different owner.
Changing the owner to the one that owns the jobs resolved the problem.