SQL Server Execute Permission Denied
I found the issue through screenshare with a user. The ODBC DSNs on some client machines were set up to use Windows Authentication, and the ODBC implementation in the applications was rather simplistic, so when running the application it was using our Windows logins. It worked for me since I am sysadmin on the database server.

The ODBC DSN setup has been changed to use SQL Authentication with a username and password, and now it works.