Ok, I've confirmed that one of the users did not have the appropriate access to the site. I had invited him to join the site, but the invitations are not working properly so he couldn't accept it, and I guess that the system doesn't do any thinking to associate that user to the invite (which can't seem to be accepted) if they join the site on their own…
That said, using IE8 he now has no issues uploading documents. The other use unfortunately, is using firefox and set up his own site, on which he's the site manager, and he's still unable to upload documents. I've mentioned that he should try disabling some of the addons, or try IE, but he's yet to do them. Does anyone know of any firefox specific issue, or addon issues that could cause problems with the document library??