row-level deadlock problem

Hello.
I'm running postgresql 7.4.6 on linux 2.4.21(Redhat Enterpise 3).
I have problems with deadlocks caused by(at least I think so) row-level
locks and I can't find the reason.
First I thought this has something with fk constraints, but removing it didn't change anything.
Here is simplified schema of my table:

CREATE TABLE stats (
counter integer,
color varchar(6),
shape varchar(6),
size integer,
d date
);

There are non-unique btree indexes on color,shape and size. There is no
primary key.

This table is modified in plpgsql function, launched like this:
# SELECT updatestats('red');
All statement run in auto-commit mode, there is no explicit BEGIN/COMMIT anywhere.
Function updatestats goes like this:

CREATE FUNCTION updatestats(text) RETURNS integer AS '
DECLARE
color_var ALIAS FOR $1;
BEGIN
UPDATE stats SET counter=counter+1 WHERE color=color_var AND shape IS NULL AND d=current_date;
IF NOT FOUND THEN
INSERT INTO stats (color,counter,d) VALUES(color_var,1,current_date);
END IF;
RETURN 1;
END;
' LANGUAGE plpgsql;

Everything is ok until function updatestats is called frequently, > ~ 3 times per second.
Then I get following error:
postgres[2247]: [89-1] ERROR: deadlock detected
postgres[2247]: [89-2] DETAIL: Process 2247 waits for ShareLock on transaction 148407635; blocked by process 2248.
postgres[2247]: [89-3] Process 2248 waits for ShareLock on transaction 148407641; blocked by process 2247.
postgres[2247]: [89-4] CONTEXT: PL/pgSQL function "updatestats" line 4 at SQL statement
Last query for both childs is the same:
UPDATE stats SET counter=counter+1 WHERE color=$1 AND shape IS NULL AND d=current_date
called from: SELECT updatestats('red');
It always locks at first UPDATE statement.

I don't understand where is a deadlock possibility in such simple function. I know that waiting for share lock on transaction means waiting for row-level lock acquired by this transaction. There's no explicit locking, no SELECT FOR UPDATE statements, all fk constraints has been dropped.
Table stats is also modified by other functions, but I have deadlocks only for statements calling updatesstats, always two calls with the same 'color' argument.
Am I missing something obvious? I have no idea what can cause these deadlocks and how to avoid them.
Number of deadlock events during one day is so big that it looks like it happens everytime two updatestats function are running concurrently.
All sugestions are welcomed, thanks in advance.
--
Kamil Kaczkowski
kamil(at)kamil(dot)eisp(dot)pl