The EXECUTE permission is denied on the user-defined table types?

If your stored procedure is using dynamic sql, meaning the @sql is generated and then executed via exec @sql, you will need permission granted on the underlying tables.

One work-around is to modify to stored procedure to run as a different user. If you make it run as SELF, it will be ran underneath the creator of the stored proc, which is extremely dangerous. Still, if you have no other option:

CREATE PROCEDURE dbo.usp_Demo
WITH EXECUTE AS SELF

I really hope you've solved this by now, seeing as the question is almost 4 months old, but in case you haven't, here's what I think is the answer.

GRANT EXEC ON TYPE::[schema].[typename] TO [User]
GO