Sorry uglyb0b, no go. I am having the same issue, and nothing has worked so far.
I created a subfolder in the Root called "Documents" (I can't see a Documents/<moduleid> folder in my file manager, even after adding the Documents module). I then created a security role that was automatically assigned to all of my users. I gave that role the permission to view/write to the subfolder. When logged in as this role, I can see the drop-downs to select files, but nothing to upload a new file.
I deleted the original role I made, and remade it with a different name and without automatically assigning it. I then manually assigned one of my users to the role, and recreated the folder permissions. Again, there is no "Upload New Document" link. I made sure the module itself had the right permission settings (for the new role to be able to edit it), but still no link.
I am using version 3.0.13, with the default Documents module in that version.