Well, one revelation ... if the user logs into the machine once, they can then login into SQL Server and runs queries with no errors. However, once the server restarts, they get the error again, unless/until they log in to the machine directly one more time. It doesn't seem like that should ever be necessary, and I have no idea why that would change anything.