O material em contrib não são executados automaticamente. Você tem que executá-lo você mesmo para instalar as funções. Não conheço a versão 8.4, mas na versão 8.3 parece instalar apenas por banco de dados, então abra o banco de dados que você está usando no psql e emita o comando \i /usr/share/postgresql/8.4/contrib/uuid-ossp.sql