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).