Tripti_LPM,

Was the client doing reciprocal linking? Linking out to bad neighborhoods can have consequences.

What about the anchor text? Are those links using anchor text that may have altered relevancy score for the page?

Perhaps you should meet with the client and ask them to describe in detail the quality issues they feel negatively impacted the previous campaign. Keep in mind that they may be testing you to see if your are honest.

Links go bad when they are deleted from websites or blogs. There are certain cases that a webpage is deleted from a website or blog and the link get deleted.

Now it is not possible that all the pages got deleted. Still the previous link builder might have played trickery and got temporary links from other known webmaster.

After the contract period the link were deleted and the link builder was away taking his money.

There can be any more cases or client is not giving other useful information or trying to get negotiations

Tripti, you'll need to explain to your client that no inlinks can harm him, or penalize him in any way. The most that can happen is that the links will be devalued, or negated.

For example, if you had a site ranking well on a number of spammy links for a long time, and Google ended up devaluing all these spammy links and your rankings dropped, that wouldn't be due to any "penalty", it would be due to the spammy links being devalued.

Are you sure the links are still there?
However, the solution for this is keep on adding links.

well, lets have an example. The domain name is myfavoritetobacco.com and the domain is built on the same keyword, but links start adding negative impact when the anchor texts are not related, like adding links with keywords best laptops, plastic buckets, puppy biscuits, fish food etc. The examples are extreme cases which none of the seo do, but also numerous links with same anchor too can raise red flags with google, say over seo link building with anchor tobacco sales can also lead to negative ranking.

All links are live and the anchor text he is using is also relevant to the webpage. Now, he is requesting his previous vendor to remove those links.

I think, it is quite difficult to convince these types of clients and we should educate them properly before starting their campaign.