Trigger to prevent column value from A to B, and from B to A
Based on what you want to accomplish logically, shouldn't:
IF OLD.status = 'Cancelled' THEN NEW.status != 'Accomplished';
END IF;
IF OLD.status = 'Accomplished' THEN NEW.status != 'Cancelled';
END IF;

actually say something like this?
IF OLD.status = 'Cancelled' AND NEW.status = 'Accomplished' THEN RETURN OLD; -- Set A = A when trying to set it to B
END IF;
IF OLD.status = 'Accomplished' AND NEW.status = 'Cancelled' THEN RETURN OLD; -- Set B = B when trying to set it to A
END IF;

My syntax might be slightly off for PostgreSQL, but my point is isn't this the kind of logical expression you're looking for? (You shouldn't be doing a boolean comparison in the THEN clause, which I think is why it's mad about the !=.)