Anyway, I installed the Fences 3.1 beta hoping that this issue was resolved, but unfortunately it was not. It would be really nice if this could be fixed.
It never was a problem with Fences. Almost every time we see this its because people have Fences to run as admin but should not:

Sean Drohan
Stardock Support Manager
My steps are the following:
1. Install Fences.
2. Reboot when prompted.
3. Log in
4. Get two UAC prompts. Allow or Deny, doesn't seem to affect whether Fences works or not (but I could be mistaken)
5. Look at the properties on Fences.exe, the "Run this program as an administrator" checkbox is NOT checked. 
6. Uninstall Fences
7. Reboot
8. When logging in, I no longer get any UAC prompts.
Is there any sort of logging information or other data collection I could do to help? I'd really like to solve this issue.