You write that the user had access to the table before you moved it into a new server. Did you re-create the user on the new server, or did you bulk in users from the old server?
If you created a new user and then restored the database that he/she had access to, the user wont have the same sid anymore. Same username but different sids.
If you, in the database that the "lost" access is run:
You will find users that are present in the database, and as logins on the server without matching sids. Have a check in book online how to fix those.
About the exexute right on a stores procedure and it's underlaying tables, I do completly agree about the owner change that has to be the same if you don't use seperate rights on the underlaying objects. But if a stored procedure or view use tables/views/sprocs in another database on the server you have to explicit set correct rights on those objects in the other database(es).
___the truth is out there___