There are many possible points of failure here, and strict would have caught at least one or two of them, but not all. Warnings would have helped too. But again, there are things that are plain old logic errors which wouldn't be caught by strict and warnings.
Top down:
my @parent_list = ""; So do you want to initialize the first element of @parent_list to the empty string, all elements, or does it even matter? With Perl, declared but not initialized arrays are innocuous. It's not like C where you could end up with the litter from some previous process. However, sometimes computations are made easier by pre-filling an array with something as opposed to nothing, and if that's what you're trying to do, you should realize you're only filling one element.
while ($taxId = $taxId1){ Two problems here. First, you're doing an assignment, not a comparison. You probably wanted the relational == operator. Also, some have mentioned that strict would have caught the fact that $taxId1 isn't declared within the sub. But that's forgetting that it might be a global that is being absorbed into your sub, which is a legitimate possibility although it may not be good maintainable style. This is actually a case-in-point example of why not. If you're using a global (or lexical from a broader scope) within your sub, you are getting action from a distance, and you were unable to post an example that reflects the entire encapsulated problem.
That's not to say there isn't a place for such constructs, and maybe you have one of those places. It seems unlikely, but who are we to say? But the point is that such action at a distance has made it difficult for us to see all potential problems. ....that's ok, you gave us plenty of them to chew on that we can see.
my $parent = `getz "[taxonomy:$taxId1]" -f pid`; I don't know what this does, but that's not my concern. My concern is that you don't test whether you got a valid return value in $parent.
$parent =~ s/PARENT ID :/ /; (I fudged by holding down the space bar) Ok, here's another problem. Once again, you're not actually verifying that any action actually occurred. Do you know for sure this substitution worked? It may have failed, and you can test for that. Also, all those embedded spaces ought to be either replaced with a generic quantifier such as \s+, or a specific quantifier such as \s{24}, so that it becomes easier to debug. Finally, is PARENT ID the literal text, or is it PARENT_ID? I don't know (and presumably you do), but it's a possibility you might need to double-check.
$taxId1 = $parent; Here, once again, we don't know where $taxId1 is declared. Is it set up at a broader scope? Is this a part of a lexical closure? Is it a package global? Or is it a typo? If it had been passed as a param, we might have been able to tell, or if you had posted the portion of code that sets it up.
Sub getDistance() is accepting a scalar value ($id) from getParent(), but getParent() returns a list. That may be desired behavior, but it may be a bug. It could be that it's doing exactly what you want it to. Why are you building a list then in getParent()?
until ($id eq $common_node); We don't know the answer to this question (only you do), but do you need string 'eq' or numeric '==' for your comparison here? In your first sub you're using a '=' comparison for $taxId, and $id is presumably the same type of value. '==' is probably what you intended to use in that sub. So why is '==' ok there, but 'eq' needed here? What changed?
Some of the issues I mentioned are more likely culprits (such as not checking the return from your shell-out, and not verifying that your substitution worked), and some are less likely culprits. But I tried to give a list of the potential issues I see so that you can start tracking the issue down more systematically.