Other related content block using taxonomy
I finally figured it out.


Add the fields to your view (title, body, etc)
add a relationship to "Taxonomy terms on the node" (do not check required)
add the arguments (now contextual filters) the "Taxonomy term: Term ID" (use relationship)
set "Provide default value" to "Taxonomy term ID from URL"
uncheck (to save on the load, optional) "Load default filter from term page"
check "Load default filter from node page, that's good for related taxonomy blocks" 
set the "Limit terms by vocabulary" and pick the vocabularies
select "Filter to items that share any term"
Scroll down to the "More" section and check "exclude" that way all TIDs will be shown, but the one on the argument.


Note: I also added the exclusion on the NID of the node where I am showing the block with the other related nodes tags with terms from the same vocabulary.

Thank you.