Postgres decide verificar restrições do tipo IMMEDIATELY em um momento diferente do proposto no padrão SQL.

Especificamente, a documentação para SET CONSTRAINTS afirma (grifo meu):

O Postgres escolhe executar esta consulta usando um plano que resulta em uma colisão temporária para sort_order e IMEDIATAMENTE falha. Observe que isso significa que para o mesmo esquema e os mesmos dados, a mesma consulta pode funcionar ou falhar, dependendo do plano de execução.

Você terá que fazer a restrição DEFERRABLE ou DEFERRABLE INITIALLY DEFERRED , que atrasa a verificação da restrição até o final da transação ou até o ponto em que uma instrução SET CONSTRAINTS ... IMMEDIATE É executado.

Adendo do comentário de @HansGinzel: