Postgres INSERT ERROR: permission denied for schema public

In Postgres I created the following table inside a db called testing:

CREATE TABLE category_google_taxonomy (
    category_id integer references category ON UPDATE CASCADE ON DELETE CASCADE,
    google_taxonomy_id integer references google_taxonomy ON UPDATE CASCADE ON DELETE     CASCADE
);

When I try to populate the table:

INSERT INTO category_google_taxonomy (category_id, google_taxonomy_id) VALUES
(1,7),
(2,12);

I get the following error:

ERROR:  permission denied for schema public
LINE 1: SELECT 1 FROM ONLY "public"."category" x WHERE "category_id"...
                       ^
QUERY:  SELECT 1 FROM ONLY "public"."category" x WHERE "category_id" OPERATOR(pg_catalog.=) $1 FOR SHARE OF x

I read up a bit and eventually granted ALL PRIVILEGES out of exasperation, but it still doesn't work:

testing=# GRANT ALL PRIVILEGES ON public.category TO testing;
GRANT

testing=# \dp category_google_taxonomy
                                   Access privileges
 Schema |           Name           | Type  |    Access privileges    | Column access privileges 
--------+--------------------------+-------+-------------------------+--------------------------
 public | category_google_taxonomy | table | testing=arwdDxt/testing | 
                                           : super=arwdDxt/testing 


testing=# \dp category
                           Access privileges
 Schema |   Name   | Type  |   Access privileges    | Column access privileges 
--------+----------+-------+------------------------+--------------------------
 public | category | table | testing=arwdDxt/super | category_id:
                                                :   testing=arwx/super
(1 row)

On @Daniel's suggestion I tried GRANT USAGE ON schema public TO super;, now when I run the INSERT command I get:

ERROR:  permission denied for relation category
CONTEXT:  SQL statement "SELECT 1 FROM ONLY "public"."category" x WHERE "category_id" OPERATOR(pg_catalog.=) $1 FOR SHARE OF x"

Here is the relevant part of \d:

public | category                               | table    | super
public | category_google_taxonomy               | table    | testing

Assuming the username is testing, you probably want to do:

GRANT ALL ON schema public TO testing;

Note about granting ALL PRIVILEGES: you don't say on what this GRANT command was applied. Assuming it was ON DATABASE..., it just means CONNECT, CREATE and TEMP privileges, nothing about the public schema or any other contained object, which is why it "doesn't work".

EDIT: when that's not sufficient

If the tables referenced by the foreign keys are not owned by testing, their owner needs also to have the USAGE privilege on the schema in order to look up the referenced tables.

It's not obvious from the result of \dp (the result of \d would tell for sure) but if category is owned by super and that user also has no privilege on the schema, you'd need to assign it with:

GRANT USAGE ON schema public TO super;

I managed to solve this by doing:

ALTER TABLE category OWNER TO testing;

After which the INSERT went smoothly. I am concerned that I may have broken other things, by changing the owner from super, but that remains to be seen.