If I understand you correctly:
1. Users with their usernames added to this rule can browse the Internet through TMG. Correct?
2. How does the rule look like? What did you add? Can you please show us how the rule looks like?
3. When using live logging in the TMG console, what happens when you try to browse the site?
a) Denied by the correct rule?
b) Denied by default rule?
c) other? Please then share what TMG logs.
If the answer to #1 is yes, then DNS is not your issue. If the answer to 3a is yes, then your rule configuration is wrong. If the answer to 3b is yes, then your request does not match the rule (or any other).
In any case, you need to share with us how the rule is configured. If not, all we can do at best is guess. The above does not give enough information.