More investigation helped me find the easy workaround. UAC is a strange bird. Sometimes it pops up, and asks for what you think are administrator credentials, but allows you to type the current non-admin ones and it works. That seems to be the case here.
For now, I guess our users can use WSAM if they retype their credentials each time they launch it. It still seems like a waste of time and will definetely generate support calls, but at least they can work.
If someone knows a way to get rid of this popup all together, I would love to hear it.
