If the users aren't getting in via another security group, here's my recommendation:
1) remove the security group with the DENY. SQL Server is based on an explicit permission model. In other words, if I didn't give you or a security group you are a member of direct permission to do something you can't do it.
2) Have your AD folks create a separate group for the head guy who wants permission. Insist on managing only be Windows security groups.
3) Grant the security group the ability to connect to the database, create a database role with the appropriate permissions, and make the security group a member of the role.
This is the best practice because it is the cleanest to manage from a security perspective.
K. Brian Kelley
@kbriankelley