PostgreSQL CHECK constraint is evaluated wrongly
Well, your query here:

return NOT Exists (
    Select 1 
    FROM example_table AS a, example_table AS b 
    WHERE a.id != b.id AND a.value = b.value);


is not going to see the not-yet-inserted row, which is why it returns true on this second INSERT in your example:

insert into example_table (id, value) values (1,0);


Now, you could almost fix this by hacking up the query to something more like:

CREATE OR REPLACE FUNCTION checkunique(in_value integer)
RETURNS boolean AS
$BODY$
begin
    RETURN NOT Exists (
    Select 1
    FROM example_table WHERE value = $1);
end
$BODY$
LANGUAGE plpgsql STABLE;

ALTER TABLE example_table add constraint unique_value check (checkunique(value));


However, this is really not what CHECK constraints are supposed to be used for, and it actually introduces a race condition if you have multiple transactions writing to example_table at the same time (can you see how?). Use the UNIQUE constraints that PostgreSQL provides. If your values are too large for the UNIQUE constraint's B-Tree index, create the UNIQUE constraint on an MD5() of the value.