I checked in the source code of my posts and discovered that the plugin was adding nofollow only up to 4 links at each post. It should be adding it to all of them.
The weird thing is that after I tested 6 "nofollow-like" plugins I saw the same thing hapenning: only 4 of all the links on the post had the nofollow parameter on its output.
I think my link URls might be to long and wordpress is having some kind of issue processing it, could you please check for me if there is a solution?
I pasted a slice of a typical post of my that does that in here so you use as test content.