Relation does not exist for some users
What you see typically happens when the non-privileged user doesn't have schema level privileges.  In this case, they cannot list the objects inside the given schema - with the command you tried.  See the below example:

-- as a superuser, for example
CREATE DATABASE test;
\c test
CREATE TABLE public.blah (id integer);
REVOKE ALL ON SCHEMA public FROM PUBLIC;

CREATE USER u WITH PASSWORD 'u'; -- don't do this in production

-- connect as u
\c test u
\dt
No relations found.

-- but:
\dt public.*
       List of relations
 Schema │ Name │ Type  │ Owner  
────────┼──────┼───────┼────────
 public │ blah │ table │ dezso


See what the documentation says:


  USAGE
  
  For schemas, allows access to objects contained in the specified
  schema (assuming that the objects' own privilege requirements are also
  met). Essentially this allows the grantee to "look up" objects within
  the schema. Without this permission, it is still possible to see the
  object names, e.g. by querying the system tables. [...]


\dt does the latter, namely queries pg_class and pg_namespace to find matching objects.  Apparently, when the schema name is not specified, the system wants to hide objects from view.