D6: Create block view which returns all nodes with related terms
You probably have to do the follwing:


create a view
add a block to that view
add a contextual filter (in Drupal 6 it is an Argument)
configure it with:

Action to take if argument is not present: Provide default argument
Default argument type: Node ID from URL
Validator: taxonomy term
You can use Term ID from the URL, or try to use the term name.



Then you have to save and configure the block to show on the desired page...

These settings in Drupal 7 (more or less, there are some slight differences in interface) work for me...