1script - 4:28 pm on Apr 17, 2012 (gmt 0)
I just found out I had an unatural link profile message in Webmaster Tools from Sept 2011.
I suspect you had better start here.
My personal impression has been that these link notifications come terribly late, something like months after the fact. By the time you get the "unnatural links" notice, the damage has already been done. So, if the OP hasn't seen any problem between Sept. 2011 and now, the links are not the immediate culprit here although it stands to reason that they may still play a role by perhaps pushing the site over some "guidelines compliance" threshold when you combine them with some other violation.