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.