Since you didn't specify any other permissions you gave or denied to the user group AD\Users, I'll assume that they are memebers of db_datareader and public and have no other specific permissions.
To perform my test, I used SQL Server 2008, not R2 and started out with a completely new user group, database, schema and stored procedures.
As sysadmin
Created a Windows Group called AD\TEST_USERS in Windows
Created a login from that Windows Group in SQL Server
Created a test database TEST
Added AD\TEST_USERS as a member of public and db_datareader on the TEST database
Created a schema called XTR
Added two stored procedures sp_1 and sp_2 to XTR
As a member of AD\TEST_USERS
Opened up SSMS
Opened up the TEST database and expanded stored procedures. Nothing was visible
As sysadmin
GRANT EXECUTE ON OBJECT::XTR.sp_1 TO [AD\TEST_USERS]
GRANT EXECUTE ON OBJECT::XTR.sp_2 TO [AD\TEST_USERS]
As a member of AD\TEST_USERS
I refreshed the stored procedures and now see XTR.sp_1 and XTR.sp_2
As sysadmin
DENY EXECUTE ON OBJECT::XTR.sp_1 TO [AD\TEST_USERS]
As a member of AD\TEST_USERS
I refresh stored procedures in SSMS and no longer see XTR.sp_1 but I do see XTR.sp2
Doing the same steps as you on my SQL Server 2008, simply denying EXECUTE on one stored procedure did not make the other stored procedure invisible in the same schema to members of my test group.
Ok, on the basis of the above comment and as per my suspicion - it seems as though you are trying to execute dynamic SQL within your stored procedure.
What you need to remember is that when you do this it does not get executed within the context of the stored procedure - it gets executed within a new session. Because of this, the fact that the statement is being called within a stored procedure is a moot point, and you will need to grant explicit permission on the objects that your dynamic SQL is using.
If you don't want to do this I would refactor your stored procedure to not use dynamic SQL.
The below link from Microsoft should help you with your problem:
PRB: Security Context of Dynamic SQL Statements Inside a Stored Procedure (Wayback Machine archive)
This behavior occurs because a dynamic execution query (sp_executesql or EXECUTE) executes in a separate context from the main stored procedure; it executes in the security context of the user that executes the stored procedure and not in the security context of the owner of the stored procedure.
This is also discussed in the (more current) Microsoft Docs article:
Writing Secure Dynamic SQL in SQL Server
Executing dynamically created SQL statements in your procedural code breaks the ownership chain, causing SQL Server to check the permissions of the caller against the objects being accessed by the dynamic SQL.
Best Answer
That's PowerQuery. Just ran through that on Excel, and stored procedures don't appear, but Table-Valued Functions do. And you can call a stored procedure, but it won't show up in the query designer. You just enter 'exec dbo.Proc1' in the SQL Statement dialog: