Cannot find the object because it does not exist or you do not have permissions. Error in SQL Server

I found a reason why this would happen. The user had the appropriate permissions, but the stored procedure included a TRUNCATE statement:

TRUNCATE TableName

Since TRUNCATE deletes items without logging, you (apparently) need elevated permissions to execute a stored procedure that contains it. We changed the statement to:

DELETE FROM TableName

…and the error went away!