Display the title of related nodes from taxonomy in block
If I understand your question correctly, you can just use Views to accomplish this.  

To display a block that lists other node titles with related taxonomy terms:


Create a Block View
Add the field Node:Title (make it link to its node)
Add the argument Taxonomy: Term ID
Configure this argument as follows:


  
  Check Provide default argument  
  Select PHP Code  
  Add the following code:
  


$node = node_load(arg(1));
  if($node) {
    if ($node-&gt;taxonomy) {
      foreach($node-&gt;taxonomy as $term) { $terms[] = $term-&gt;tid; }
      return implode('+',$terms);
    }
    else {
      return;
    }
  }
  else {
      return;
  }


  
  Check Allow multiple terms per argument  
  Check Reduce duplicates
  

Now you need to add the second argument in order to exclude the current node from the list. Click [+] button of the arguments section.
Select Node:Nid
Set the "Action to take if argument is not present" to Provide default argument
Set the "Default argument type" to Node ID from URL
Check Exclude the argument
Save your view


You can customize this however you like, such as filtering to a specific content type (ie "News"), can filter by post date, sort by: post date, random, etc.

For a whole discussion on this see http://drupal.org/node/65375

(Sorry for the poor code formatting, not sure how to format code inside a blockquote and list)