INSERT/UPDATE stored proc deadlocking itself
I think you will find this pattern better:

BEGIN TRANSACTION;

UPDATE dbo.OrganizerDataDependencyChange WITH (HOLDLOCK)
  SET Updated = GETDATE()
  WHERE TableID = @TableID
  AND [Database] = ISNULL(@Database, '');

IF @@ROWCOUNT = 0
BEGIN
  INSERT INTO dbo.OrganizerDataDependencyChange
      ( TableID, [Database], Updated )
  VALUES(@TableID, ISNULL(@Database, ''), GETDATE());
END

COMMIT TRANSACTION;


Stop thinking about having to "check" if there is a row to update, and then updating it, which can lead to two full scans. Just try to update it. If no rows are updated, no harm, no foul - you can simply perform an insert (I talk about this a bit here).