The problem was being caused by the fact that the root site on the server did not grant the users read access.
For example, imagine they are trying to upload to:
The user has full permissions on mysite, but if they try to access http://server/ they get permission denied. Even though the user can upload to mysite, they cannot upload with SimpleIndex because the client objects require permission on the root site.
Granting the users at least read access to the root site at http://server/ resolves the issue.