Rehabilitate a 13 year old branded site or start again?

Selected answers from the Dumb SEO Questions Facebook & G+ community.

• 
  Gabriel Hernandez: Hello, I'm new to this community, here is my dumb question.
  We have just found out by our SEO guy we just hired that our home page has been penalized by Google and our Home page is not being indexed. We have about 500 bad back links coming into our site. He recommends instead of trying to remove the back links, we should start fresh with another site. ;
  My reservation against that is that we have had our domain for about 13 years and it is decently branded (not great). ;
  I would like to know your thoughts/ opinions in doing this strategy.
  Thanks
• 
  Mehdi Mirza: +Gabriel Hernandez ;I would suggest using Google Disavow Tool which is used in cases like yours, click the link and follow the steps to get your domain back in shape : )
  https://support.google.com/webmasters/answer/2648487?hl=en
• 
  Jim Munro: This is a good question, Gabriel. Would you be willing to share your url so we can look at it for you? If you don't want to do this publicly, PM it to me and it will only be known to our panelists on tonight's Dumb SEO Questions Hangout on Air.
• 
  Gabriel Hernandez: Sure no problem. It is www.MattressMakers.com ;
  What time is the Hangout?
  +Jeffrey Foxworthy ;no he does not build websites, he is going to do the exact same site just change the content.
  +Mehdi Mirza ;From what I've read the disavow tool is not really recommended. It should be used as the last resort.
  Thanks guys!
• 
  Mehdi Mirza: +Gabriel Hernandez ;I am really surprised to hear that Disavow tool is not recommended. ;
  Please read experts view on the tool here ;
  http://searchenginewatch.com/article/2309486/Matt-Cutts-Use-the-Link-Disavow-Tool-Even-if-Your-Site-Hasnt-Been-Penalized
  
  Ask your SEO person, how did he come to the conclusion that your website is penalized?
  Did you see a Traffic Drop in Google Analytics?
  Did you receive an email from Google, if your website is using Webmaster Tools?
  
  Simple test, run this in Google Search ;
  site:www.mattressmakers.com
  I see that most of your pages are indexed.
  
  If you are not using Google Webmaster tools, then please use it and you can see the status of your indexed pages there as well.
  
  Let me know if you need any assistance