EXEC Permission On A SCHEMA COLLECTION???

I have a permissions problem with a table/procedure that I hope someone can help me with.

To set the scene .......

All my procs/tables/functions etc are owned by dbo.
I have a windows security group that is granted permissions to EXEC all procs. No one has permissions to tables.
I have a table that has an XML column and the column has a schema collection bound to it.
The table has a computed column that relies on a function to extract a datetime element from the XML in the XML column and I have an index on this computed column.
I have a proc that selects from this table and uses the computed date column for filtering. However, the select statement is build dynamically and uses sp_execute to perform the SELECT. This of course breaks the ownership chain.
To fix the above I have a user that was created from a certificate and the above proc is signed with the certificate. The user is granted select privileges on the table. This fixes the problem. (In fact, all procs/functions/triggers are signed in this way).

Now (finally) the problem ....

When I run the above proc as admin, it works fine.

When I run it as a member of the security group (mentioned earlier) I receive ...

EXECUTE permission is denied on object 'my_schema_collection', database 'mydb', schema 'dbo'

The 'my_schema_collection' mentioned above is the schema collection to which my xml column is bound.

What? How can I grant EXEC permission to a schema collection?

Anyone have any ideas?

Thanks,

~swg