Pole-zero cancellation Paradox
It's not a paradox. Adding that zero makes it a completely different system. I checked in MATLAB and both plots look right (for an arbitrary a and b, |b|>|a|). That new zero annihilates with a pole which is why you are getting a different root locus plot. Adding LHP zeroes, among other things, improves the stability of your system, though at the cost of transient performance.