Have you checked the value filled in for 'metadata status', 'active status' and 'usage rights'?
By default, non-admin users cannot see assets that are marked 'metadata status incomplete'. This can allow a workflow for uploaders, to only change the status to 'complete' once all the metadata is filled in and they are happy to release the items to the other users.
Non-admin users may also be restricted to only seeing 'internal' usage rights and 'active' active status assets.
This is configurable from the Admin area, in the Admin -> Groups -> Attribute Exclusions area. If you tick any of the boxes, the users in that particular group will be excluded from seeing assets with that particular value.
Note that if a user is a member of another group for which the attribute exclusion settings allow the asset to be seen, then that takes priority and the user will be able to see the asset.