I propose some code changes to improve error handling, debugging and especially to only write a users title to the db if it actually needs to change.
Current version:

function user_titles_set_user_title($uid) {
  $tid = user_titles_get_user_tid($uid);
  db_query("UPDATE {user_titles_users} SET tid = %d WHERE uid = %d", $tid, $uid);
  if (!db_affected_rows()) {
    db_query("INSERT INTO {user_titles_users} (uid, tid) VALUES (%d, %d)", $uid, $tid);
  }
}

Improved version:

function user_titles_set_user_title($uid) {
  if ($uid>0) {            // is the user valid?

    // only update the level if it needs changing (avoid) a DB write)
    // so first find the current level:
    $row = db_fetch_array(db_query("SELECT tid FROM {user_titles_users} WHERE uid = %d", $uid));
    $current_tid= $row['tid'];
    $tid = user_titles_get_user_tid($uid);   // next calculate the current title
    watchdog('user_titles', "update uid=" . $uid . " to new title=" . $tid . " current=" . $current_tid);

    if (($tid >0) && ($current_tid<>$tid) ) {   // is a title update needed?
      // Try an update, if that fails insert
      if ( db_query("UPDATE {user_titles_users} SET tid = %d WHERE uid = %d", $tid, $uid)) {
        watchdog('user_titles', ' title updated, affected_rows=' . db_affected_rows());

        if (db_affected_rows()<1) {   // Insert a new row, there wont be duplicates
          watchdog('user_titles', 'insert new title');
          db_query("INSERT INTO {user_titles_users} (uid, tid) VALUES (%d, %d)", $uid, $tid);
        }
      }
    }
    else {
      watchdog('user_titles', ' no title change needed for uid ' . $uid);
    }
  }
  else {
    watchdog('user_titles', "warning _set_user_title uid not set", array(), WATCHDOG_WARNING);
  }
}

The watchdogs are there to help understand the flow..