TRY .. CATCH sometimes fails to catch PRIMARY KEY VIOLATION
Not sure if this is the issue, but you should use ERROR_NUMBER() not @@error in your catch block.

In any case something like this should work reliably, without PK voliations:

SET nocount ON;
begin transaction
IF NOT EXISTS(SELECT * FROM MyTable with (updlock, holdlock) WHERE ID = @ID)
begin
  INSERT INTO Table(ID, Value, TimeChanged) VALUES (@id, 'xxx', GETDATE())
END 
else
begin
  UPDATE MyTable SET Value = 'xxx' WHERE ID = @ID AND TimeChanged &lt; GETDATE()
end
commit transaction