Well, they've apologised, explained what they were trying to do and sent wine and chocolates over.

I've got sympathy for them here: spam sites linking to you is a serious problem. One day the spam site has (undeserved) link juice. The next, Google's ban hammer comes down and you get unfairly penalised.