Do these sample URLs bring you any traffic? I guess I am wondering whether it would be worthwhile to send another reconsideration request explaining how you got these links and telling them they are natural and you may have stronger point especially if these links send you traffic.

Before doing this, it would be also worthwhile to scrutinise these sites in their example that link to you. Where I am getting at is - if these sites have what could be considered unnatural links to some other websites, Google may just assume that the link to you is also unnatural.

The example links in the warning message are generated automatically, and there have been other reports like yours where the example links are actually perfectly good links. But the fact that you got the warning indicates that Google's system has found some suspicious links to your site, so I think it would be best if you checked all of your links for problems. And be sure to keep a record of what you've done to investigate the issue so that if Google penalizes you, you can show them that you've been working on it since you received the warning.

With so many "false-positives" lately, one has to question if Google is using its marketshare to scare webmasters into not linking to one another. A greater dependence on search would be the result, and it's possible that this is what Google is going after. The seed was planted well over a year ago, and these unnatural link warnings, even if they are wrong, is the water that allows this fear to grow.

Do not disavow the links. If people start disavowing legitimate links, we as webmasters will sink further into the cesspool that Google created. Submit a reconsideration request and explain your case. Whether the links give you traffic or not is inconsequential. The point is if they are natural or not. Please report back with your results.

A word of caution though. Do not post your URL in Google's webmaster help forum to seek a quick resolution. I've read some blackhatter forums where they are link bombing the people who post in Google's help forum.

Check out the link profile of the site whose links Google doesn't like (and use one of the paid link databases for this, not just Google or one of the free ones as their data is very incomplete).

You might find that this genuine-looking link is from a site that is judged to be a bad neighbourhood.

If you are satisfied that the links are genuine and the site is genuine I'd try to let Google know that they've got it wrong. It's hard enough to get links without disavowing freely given ones!

well i can say that google algos recently sucks so bad

with many cases i saw, they are marking valid backlinks as spam

God knows they probably mark spam backlinks as valid

it is all messed up

Check out the link profile of the site whose links Google doesn't like

I don't see how this really has any bearing on natural links being identified as unnatural, and I surely don't see how many small businesses/webmasters can inspect the backlink profiles of not only their sites but also of everyone who links to them.

Those who run quality sites, and I'm not talking about the typical thin sites that are produced these days, will have a certain level of unnatural links. Providing depth, useful details, videos and detailed photographs has its drawbacks. Often link spammers will throw other links in their spam pages to make their spam appear real with authoritative references. These types of links, which are unnatural, do trigger penalties that demote innocent sites that are linked to in spam pages merely because they have taken the time to innocently produce quality content.

The bottom line is that Google has webmasters running in circles chasing their tails like dogs. Sooner or later these dogs will grow tired and pause to think about what they are doing, why they are doing it, if they can ever catch their tails and what benefit it produces if they do.

with many cases i saw, they are marking valid backlinks as spam

@MasterOfPuppets maybe we are witnessing a very nasty side of their Disavow policy/plot/plan whatever you wanna call it... If a webmaster went looney about his/her backlinks and disavowed them and Google took them seriously without having a proper review mechanism with PROPER safeguards.

Thinking this is what happens when they rely so much on backlinks for their SERPs and they are so prone to link spammers despite all the tweaks in their Penguin algo... IMHO that is ;)

Their urgency to deal with it has side effects like the one we discuss now..

<EDIT>Added last sentence above</EDIT>

@mcskoufis that makes sense. i can clearly say their algo is extremely flawed when weighting backlinks as spam or natural

If you are satisfied that the links are genuine and the site is genuine I'd try to let Google know that they've got it wrong. It's hard enough to get links without disavowing freely given ones!

The backlinks of the linking site, though, inevitably affect how Google looks at backlinks from that site. Remember that discussion we had recently about "upstream links"?

Can hanging out on blackhat forums cause you ranking problems?
http://www.webmasterworld.com/google/4596639.htm [webmasterworld.com]

Though the premise of that thread was a little off-base, it got into an issue that Google said it was going to explore. To quote a self-quote I made in that thread...

All linking pages are subject to changing conditions upstream of them... anything from code changes to business changes to algorithmic changes, all of which can positively or negatively affect inbound link juice. Some pages have good enough content to attract inbounds once they become sufficiently visible, which can mask other upstream changes. In some market areas, links will be affected by upstream link buying and selling as well....

Well, here's the pollution flowing downstream to haunt us all.

One of Google's dilemmas here is that it can't simply ignore the fact that the links from intermediate sites, sites which are otherwise looking good, are polluted. Seemingly-clean intermediate sites are a tactic that link spammers often use, and it's very tricky, I'm sure, to weed these out. This may be an area where collateral damage is likely, but I don't know that for sure.

While I agree with FranticFish that if the particular link came naturally, you should try to let Google know... it may be more expedient simply to try to get it nofollowed. Also, check out other links from the same site, and see what the other outbounds look like. Maybe you really shouldn't want the link.

One of them even wrote a tutorial about how to use my site's app!

Yes, I can see how that would really be rubbing it in. Another possible issue, though, is that the content of the tutorial may too closely resemble your content on the same subject, closely enough that it looks like a promotional article that you may have placed yourself. How Google sees this may depend on what your other link acquisition techniques have been.

I surely don't see how many small businesses/webmasters can inspect the backlink profiles of not only their sites but also of everyone who links to them

Not for free, I'll grant you. But there is at least one tool gives diagnostics on bad link neighbourhoods (and it's also currently offering a free trial).

This is Google's mess, for sure. But in an eco-system where you are held responsible for your IBLs then checking your profile makes economic sense.

Added: just to be clear, I'm not affiliated with ANY link databases :)

Not for free, I'll grant you.

Where there is misery there shall be profiteers.

I'd really question how much upstream plays into penalties. Yes, when a probability threshold has been achieved a site's outbound links may be devalued to 0. But assigning penalties based on not where a link originates but from where the linking site's links originate from would generate wildly inaccurate results.

But in an eco-system where you are held responsible for your IBLs then checking your profile makes economic sense.

There are few other situations where you can be held responsible for another's actions, but Google is doing just that. I'm not sure if you have seen the number of negative seo companies/services growing or threads on other forums where people are hitting sites with spam links indiscriminately, but it is a growing trend to watch. Once again, where there is misery there shall be profiteers.

Agreed 100% that Google have created the misery, and therefore helped to spawn the attendant industries to ruin a site or diagnose its being ruined.

But IMO the investment in link data is worth far more than identifying bad links to your own site. As Google has not shown proper link data for years now, running these independent reports on any website is a great way to find sites you could approach, and can also inform strategy and give you ideas for content / outreach for your own site.

With so many "false-positives" lately, one has to question if Google is using its marketshare to scare webmasters into not linking to one another.

But the algo is still mainly based on links, so Google needs us linking. The problem is they have never found a good way to deal with spam links, and this is creating more and more headaches for honest webmasters. The whole thing sucks, but I don't think it's on purpose.

I also agree that you should let Google know you didn't solicit these links. Maybe also ask them why they consider them unnatural and remind them you are doing your best to follow the guidelines. I've had success with that approach, albeit under different circumstances (bought a previously owned domain, built a completely different site on it, but apparently the old owner had done wrong - submitted reinclusion explaining this, and all was well within a few days).

But the algo is still mainly based on links, so Google needs us linking.

I think Google is well beyond the point of needing us for linking. Their algo, which once relied on links, is now more focused on generating revenue. Extreme domain crowding, paid ads and listings for other Google owned properties has pushed a somewhat diversified set of organic search results beneath the fold for many semi-competitive+ queries.

For off the wall search queries, Google may be more reliant on links. But I believe right now it is who that is least penalized that will appear at the top of the search results, which in 2013 is likely to be beneath paid ads, youtube videos and big brands. In other words, beneath the fold where little organic traffic originates from and where little effort has to be put forth by Google to "please" their users.