We have set the user that runs the restore step of the job to be the DBO user.
So this is a T-SQL job step, and you have set the user on the Advanced page for the jobs step, like below? That will not work out. When you do this, SQL Server Agent will impersonate that database user and when you impersonate a database user, you are sandboxed into the current database, and you cannot access things outside of it. And since you are to restore that database, the job cannot run with that database as the current database. So this means that on top of all, you are impersonating the dbo of another user.
Just remove the Run as user and let the job execute as sysadmin, and it should run without issue.
By the way, any special reason you are setting the database to TRUSTWORTHY? This is a security risk if there are users in the that database with elevated permissions on database level, but who are not members if sysadmin.