Supondo que o nome de usuário seja testing , provavelmente você desejará fazer isso:
GRANT ALL ON schema public TO testing;
Nota sobre a concessão de ALL PRIVILEGES : você não diz em que esse comando GRANT foi aplicado. Assumindo que era ON DATABASE... , significa apenas CONNECT , CREATE e TEMP privileges, nada sobre o esquema público ou qualquer outro objeto contido, e é por isso que "não funciona".
EDIT: quando isso não for suficiente
Se as tabelas referenciadas pelas chaves estrangeiras não forem de propriedade de testing , o proprietário também precisará ter o privilégio USAGE no esquema para consultar as tabelas referenciadas.
Não é óbvio pelo resultado de \dp (o resultado de \d diria com certeza), mas se category pertencer a super e esse usuário também não tiver privilégio no esquema, você precisa atribuí-lo com:
GRANT USAGE ON schema public TO super;