After searching around google's new backlink tool I noticed that google does recognize links with the "no-follow" tag. Of course we have no idea what weight, if any, is given to these links, it's interesting to see that google does indeed "follow" and index them.
http://www.mattcutts.com/blog/google-provides-backlink-tool-for-site-owners/ "Do not assume just because you see a backlink that it’s carrying weight."
So, if you are paying for a link and notice that it has a no-follow tag...would you cancel the link, even if it is a good one?
It depends what you want from the link. If it's PR, you'd better cancel it. If you want traffic and it's giving you traffic then all's well.