Ok so last night I kind of left a short reply here and I would like for my personal illumination to augment it a little.
While a link is a link, and most people should go by this more often than they should, do not expect magic to happen.
Tommy here is providing a very special example that applies maybe for 1% of this forum or less. Not sure how many purchase forbes and the like guest posts considering the price.
So what will happen is most people will try and adapt to their own possibilities and say "ok, so no follow counts for something".
While I can't disagree that it doesn't, you have to take under consideration that a mention ( even a no follow one )from one of the pillar websites of the internet is not going to help you THAT much as you might think.
OP is talking about clients who are already doing ok, they want to secure their brand name, their presence online. They are creating a name for themselves, so do or no follow is equally the same for them.
But this too is not applicable for all. Again, we are talking about authority websites that provide some sense and quality to the web. Most of us people here run affiliate sites and cpa blogs. Securing your brand name "IsellAMAZOnthingsANdMakeMoney" won't do you any good. In 99% of these cases, even 10 wikipedia links won't help. Why? Because there is nothing to help.
On the other hand, say we have ourselves a nice blog, full of information, and it starts getting mentions ( no follow ones ) from all over the big guys left and right directly on its brand name. Then yes, in this case it would be a totally different situation. Even with no follow link, the minute that blog is going to post an article for say a low-medium keyword, they will start ranking it from position 6-12# which makes all the difference in the world.
There is one minor exception that OP left out or didn't consider worth mentioning. No follow links will help you with bing. Yes, bing, that old forsaking search engine. Somehow, its like bing doesn't care about follow tags. Everytime bing catches one decent article from no follow link, it just shoots it in the first page. Traffic from bing is not neglijable. There are cases when they make a huge difference. Personal example would be getting 200 organic peple from bing on an article per day for a specific keyword and just 30 from google. Said article being ranked up just with a bunch of no follow links.