See my approach: I wanted to order nodes like taxonomy does (descending creation time):

<?php
  function next_prev($current_nid, $created, $type, $btn_type, $label, $class) {
    switch ($btn_type) {
      case 'next':
        $sort = 'DESC';
        $sign = '<';
        break;
      case 'prev':
        $sort = 'ASC';
        $sign .= '>';
        break;
      default:
        return NULL;
        break;
    }
       
    $sql = '
      SELECT 
        tid 
      FROM 
        {term_node} 
      WHERE 
        nid = %d';
        
    $tid = db_result(db_query($sql, $current_nid));
  
    $sql = "
      SELECT 
        n.nid, 
        n.title 
      FROM 
        {node} n 
        INNER JOIN {term_node} t 
        ON n.nid = t.nid
        INNER JOIN {term_data} r 
        ON t.tid = r.tid 
      WHERE 
        n.type = '%s' 
        AND ((n.created $sign %d) or (n.created = %d and n.nid $sign %d))
        AND r.tid = %d 
        AND n.status = 1 
      ORDER BY 
        n.created $sort,
        n.nid $sort";
        
    $result = db_fetch_array(db_query($sql, $type, $created, $created, $current_nid, $tid));
    if (!$result) {
      $sql = '
        SELECT 
          name 
        FROM 
          {term_data} 
        WHERE 
          tid = %d';
        
      $name = db_result(db_query($sql, $tid));
      
      return l(sprintf(t('Back to %s'), $name), "taxonomy/term/$tid", array('title' => $name, 'class' => $class));
    } 
    else {
      return l($label, 'node/' . $result['nid'], array('title' => $label, 'class' => $class));
    }
  }
?>

and:

<?php
  $types = array('story');  
  if($page != 0 && in_array($node->type, $types)) {
    $next = next_prev($node->nid, $node->created, $node->type, 'next', t('Next in this category'), 'node');
    $previous = next_prev($node->nid, $node->created, $node->type, 'prev', t('Previous in this category'), 'node');
    echo "<div class=\"center\">$previous | $next</div>";
  }
?>