What could cause SQL Server to deny execution of a SP at first, but allow it later with no privileges change?
If the Windows user account was added to an Active Directory (AD) group in the meantime, and that AD group had permission to run the procedure, then that could create this scenario where a user gained access to a procedure with no changes within SQL Server.

Also get the network admin to check if the user logged off and on again. Group membership only gets assigned at logon so if the user was added to a group and had not logged off he would not have had that group membership in his token. -  Spörri

Related Q&amp;A: How do I assign an entire Active Directory group security access in SQL Server 2008?