The problem I believe has to do with changes on standards.
The w3 validator shoes as an error to have multiple rel="example" tags inside an argument. So when it added its no follow arguments did the following things.
Incorrect
<a rel="nofollow" href="http://www.malla-supply.com/manufacturers-abb-96?p=2" rel="next">
Correct
<a href="http://www.malla-supply.com/manufacturers-abb-96?p=2" rel="next nofollow">
To solve this I removed the code that generated the nofollow real tag {$no_follow_text} and hardcoded it manually.
This is not the best practice but works for now.