I think the answer from Alex Leith is the most likely cause of this error; the geometry_columns table/view gets created as soon as postGIS extension is created.
But it could still happen even if postGIS extension has been added, I think there are two aspects to this..
Table in different schema to postGIS
I found this could happen if the table I was importing was in a different schema to that where the postGIS extension was loaded. This meant that QGIS couldn't "see" the postGIS functions, data types and tables/views, as it assumed it was in the same schema as the database.
Got a very similar warning:-
To reproduce this, I took an existing local postgis-enabled database (with tables in 'public' schema), dropped the postGIS extension, and recreated it in a new schema, 'test')
CREATE EXTENSION postgis
SCHEMA test
VERSION "2.1.2";
Now, attempting to add a table from the 'public' schema will result in that error.
There's a setting called search_path which can be set at database level, which will allow qgis to see schemas other than the one the database is in. If you have access, something like
SHOW search_path;
will typically return something like "$user",public
or "$user",postgis
. If that list doesn't include the schema postGIS is in, that might be the problem.
Be careful tweaking that setting, I found I got QGIS crashing on opening projects with one database connection I'd altered that way. Luckily, you can remove connections without needing to open a project using the 'elephant' icon. I'll raise a ticket if I ever manage to reproduce this problem.
QGIS expects postGIS to be installed in Public schema
It also looks like qgis expects postgis to be installed in the public schema. If I created a database whose tables and postGIS were both in a schema other than public, I got the message
Database connection was successful, but the accessible tables could not be determined.
Best Answer
You also need to grant usage on your schema: