diberry - 3:15 pm on Aug 6, 2012 (gmt 0)
I would tell Google the truth, and pretty much like you've told it here.
You might emphasize that you believe these people would just 'fess up to you if they'd done this, and that you're appealing for reinclusion because taking down the links is NOT something your client has any control over.
I'd be curious to hear if you see any recovery after asking for reinclusion. When I asked for it, I honestly told them I hadn't been doing SEO, was never very good at it, and that a couple of SEO pros had looked over it for me and also couldn't see anything "spammy". I also outlined a few things I was doing to improve the site (all on-page). I got the no manual action email in response, but no recovery.