You MUST used, not only because Yahoo, Bing and others will count, but because for Google's also looks "natural".
If your site just use Follow links looks suspicious, so use it and wait for the traffic and the PR.
Agreed with Micallef, I think the whole 'You must have nofollow to look natural' attitude is BS and a waste of time. The only reason we think this is because a lot of us are blackhatting our link building.
Think about all the legit webmasters out there who have paid for their links and do legit link exchanges. None of those are likely to be nofollow and I'm certain they won't be penalized because of it.
As saady said, if the is is authority it will help your site.
Is a link from nofollow Wikipedia useless, duh!!!
[edit] M. Cutts ONLY said no pagerank is passed, he said nothing about:
a) trustrank (e.g. a link from wikipedia)
b) relevancy