You people have lost your mind. For pete's sake you cant go to a customer and say "By the way, your site is fucked, not really my fault, but you have to get another name for your business site."".
The simple fact is that you better figure out what to tell your client, and what steps top do right now.
I am not sure we have heard the whole story, you claim to have done only a little link building but mention you have SB and GSA. (but I digress)
Quit building links, that is what messed you up to begin with (at least in the manner you think link building is done).
Anyway.
First do the disavow tool and get rid of all the spammy links, be sure to get the spammy ones you built too.
Next go to Google places and build a profile for the customer. This profile will need to be used everywhere you list this business, and you need to use exactly the same information in this profile in every local business directory that you list with. List the business with Google , and do not leave anything unfilled. If they have room for 30 pictures, 22 videos, 12 pod casts, give them it.
Then do Yahoo/Bing.
Use exactly the same pictures with exactly the same tags and everything. Consistency across all listings is vital.
Do not give me that crap about directory listings not having value, this is local and local is different. And do not go spam hell out of website listing directories either, I am talking about the local business directories like Local,com, Manta, Yelp, super pages, ans such and so on. Find as many as you can and submit all the information manually, and do not vary a word of the profile, except when you add extra information, even then add all the standard information, pics and videos first, so the basic profile is always present.
Do a specific search to find directories that list people in your business. Go to and join all of these and get listings there. Join communities online that someone from this business would join and list your company anywhere that is related to your business versicle.
Search out also business communities in your local area or a state and do the same with them. These things build citations.
Get some one who really knows on page SEO, and have them optimize the home page and all core service or product pages. Do not skip this, it is more important than you think.
Create the usual social accounts, and use them FOR business. Set up Google alerts that apply to the business and city and share these things in your social media.
Keep the fact that you want to save the Whales or that Obama should be made king to yourself, these accounts are for business. Don't over share. Read that again, its even more important that the onpage. Even one innocuous political liberal or conservative comment comment will piss off 40 % of the people who read it because they are not that party.. Keep that crap at home.
In your social media you approach the world with your hat in your hand, with humility and respect, and modestly say "I am the best choice for you in the world for you for what you want done, and if you can afford me, I can work magic for your business."
Subscribe to HARO, blogger link up, Pitchrate and the such and watch for something to come along that you can pitch for this customer. Have a few pitches ready to go. Watch for chances to get him free publicity. As soon as this happens, put out a press release telling that the customer was highlighted on this website, or that tv show, or magazine.
Instead of using free press release services, pay to have this press release submitted to news feeds and aggregators as opposed to press release websites. Press releases are quickly turning into link farms, and I see no value the in the long run
Take this press release and write a story about the business appearance on the whatever, and send it to every small newspaper in your community, every radio station, every tv station, and and any newsletters that you can find in your community.
Have a Piece of original software created, say a calculator to figure the cost of new carpet if yo are a carpet guy, and build a PAD submission for it and give it away free online from the Software directories on the Internet. It must be their software, so buy it for that purpose.
That's all you get for free.
The best revenge you can do is stuffing that website right back up your competitors ass and into the top spot again. Otherwise, he won AND he gets to rent space in YOUR head.
