Problem with permissions for user
GRANTing ALL permissions for public to the database is mostly redundant (as public has connect, temporary by default, so you'd only be adding CREATE which you probably don't want to do). You probably expected a GRANT ALL on the database to result in a recursive GRANT ALL to contained schemas and tables. GRANT is not recursive, so this doesn't happen; a GRANT ALL on a database just grants CONNECT and TEMPORARY rights to the database, with no effect on contained schemas and tables.

The default GRANTs are, from the docs on GRANT:


  PostgreSQL grants default privileges on some types of objects to
  PUBLIC. No privileges are granted to PUBLIC by default on tables,
  columns, schemas or tablespaces. For other types, the default
  privileges granted to PUBLIC are as follows: CONNECT and CREATE TEMP
  TABLE for databases; EXECUTE privilege for functions; and USAGE
  privilege for languages. The object owner can, of course, REVOKE both
  default and expressly granted privileges. (For maximum security, issue
  the REVOKE in the same transaction that creates the object; then there
  is no window in which another user can use the object.) Also, these
  initial default privilege settings can be changed using the ALTER
  DEFAULT PRIVILEGES command.


So you can see you don't need to GRANT anything on the database unless you want the user to be able to create schemas, etc. You need to:


GRANT USAGE ON SCHEMA myschema TO theuser; for any schema other than public. CREATE can be granted if you want the user to be able to make tables, views, etc.
GRANT SELECT, INSERT, UPDATE, DELETE ON TABLE sometable TO theuser; for tables. I've omitted the TRUNATE, REFERENCES and TRIGGER rights as you probably don't want to grant them.
GRANT USAGE ON SEQUENCE sometable_somecolumn_seq TO theuser; for any sequences that are used in table defaults, either explicitly or via a SERIAL or BIGSERIAL column.


... etc. See the manual for GRANT linked above for full definitions of what the privileges do, which are available on which objects, etc. Take note of the wildcard ALL TABLES and ALL SEQUENCES options.

If this seems like too much hassle to do for each table, view, schema, sequence, etc, you can in Pg 9.1 and above use ALTER DEFAULT PRIVILEGES to change the default GRANTs on new objects.


The manual for GRANT
The manual for ALTER DEFAULT PRIVILEGES