If anyone's interested, here was the cause of, and solution to, the problem.
Somehow the client had told the program to run as administrator at all times, which is what brought up the UAC message, and somehow stopped it from working properly (an external Excel worksheet was supposed to be communicating with it via a DLL, which is what stopped working).
To turn this mode off, I right-clicked on my application executable, clicked properties > compatibility and unchecked the 'Run this program as an administrator' checkbox. This immediately solved the problem. You could also use the 'Change settings for all users' dialog to change this setting for multiple users.