Acho que o problema aqui é que o hstore que você tem é nulo e nulo OU algum hstore é nulo.
A melhor solução que tenho, que provavelmente não é a melhor solução, é fazer a tabela com um hstore vazio padrão em vez de permitir null. Então seus exemplos funcionam como você gostaria:
postgres=# create table htest (t text, h hstore default hstore(array[]::varchar[]));
CREATE TABLE
postgres=# insert into htest (t) values ('key');
INSERT 0 1
postgres=# update htest set h = h || ('foo'=>'bar') where t='key';
UPDATE 1
postgres=# select * from htest;
t | h
-----+--------------
key | "foo"=>"bar"
(1 row)
Infelizmente, não vejo uma maneira mais limpa de criar um hstore vazio do que
hstore(array[]::varchar[]) mas isso não significa que não haja uma maneira melhor. Você pode incorporar isso em sua atualização hstore de antes da seguinte forma:update htest set h = coalesce(h, hstore(array[]::varchar[])) || ('foo'=>'bar') where t='key';
Dessa forma, você não precisa recriar a tabela. Eu acho isso bastante nojento embora. Espero que isto ajude.
