This kind of thing is quite tricky to test.
What I generally do, when something that works for some people and not for others, is to email a var_dump($FILES) whenever something is uploaded. That should contain the error code for the upload, which may give some more information. (alternatively, you could write the vardump() to a text file and check it every now and then).
From there, you could try to find out why the upload is failing for some users.
Are you using a Flash uploader or a standard file input?