Adding column to Postgres table fails

I have a Postgres (8.4.20) table that I'm supposed to add columns to, but it seems to have some problems that I have difficulties to debug:

I'm attempting what I thought was a simple ALTER TABLE... on it:

db_name=> ALTER TABLE "marking" ADD COLUMN published TIMESTAMP WITHOUT TIME ZONE;
ERROR:  canceling statement due to statement timeout

I'm puzzled, because:

1. Although the table has (very little) data in it, it's not a `NOT NULL` column
2. I've also tried to dump the table, delete it's contents and re-run without data in it

But it still gives the same result. Here's the current schema for the table:

db_name=> \d marking
           Table "public.marking"
 Column |         Type          | Modifiers
--------+-----------------------+-----------
 link   | character varying(32) | not null
 hash   | character varying(40) | not null
 url    | text                  | not null
 blob   | text                  | not null
Indexes:
    "marking_pkey" PRIMARY KEY, btree (hash)
    "ix_marking_link" btree (link)

Sorry for the newbie question, but there's clearly something fundamental I don't understand here and I'm having some trouble getting further.

I've tried to increase statement_timeout and work_mem, but even very large values won't help.