File shares have 2 levels of access. The file share itself defines who can access the file share and what they can do. Please confirm that you have configured the share to allow read access to the files on the share.
The second level is on the file system itself. The NTFS permissions apply if the user can access the share. You also need to ensure that anyone accessing the share also has read permissions to the folder (and subfolders) of the share. Based upon your description it almost sounds like they have read file rights but not list rights to the directory which I didn't even think was possible. In the NTFS permissions UI go to the Effective Access tab under the Advanced settings and type in the name of the user attempting to use the share. Confirm they have all the necessary read rights to the folder and subfolders. I wonder if maybe they only have root folder access.