I made the mistake of authorizing LinkedIn to fetch contacts from my Gmail account ages ago - atleast 4-5 years back. If you are like me, here is a link to delete the contacts that you have not explicitly added on LinkedIn:

http://www.linkedin.com/people/contacts?sortAction=lastName&...

I had to raise a support ticket to find this link.