If it's only for newly created users then it sounds like you may have volume security set up. Perhaps, for example, your existing users belong to a group that grants them the necessary volume rights.

A note on your troubleshooting step for future reference:

Administrative rights do not automatically override all entry access or volume access rights to allow viewing a document.

For example, the privilege "Bypass Browse" will let that user look at the list of entries within any folder, but does not let that user view the documents themselves unless they have sufficient entry access rights.

Similarly, "Manage entry access rights" will let the user browse folders and modify security on entries, but does not automatically grant them the right to view the content of the documents.