I purchased a website a while back and just today realized that it has some (many actually) bad links pointing back to my site which has caused Google to flag my site as a web spam. Obviously, this has affected the traffic volume as well. Looking at the list, it would be impossible to remove most of them since I don't have any control over those accounts that were used to post these links at various sites.

Given this, what is the best way to handle this? If I change the domain name and let search engines know of my move, would it help the situation?