There are different "levels" of penalization that a site can get. Some sites will totally drop out of the search engine results after getting an unnatural links penalty, some will just lose a few positions and some will drop for just certain keywords.
If you've got self made links then Google wants to see good effort that you have removed as many of those as possible and for the ones you couldn't remove then they want those disavowed. The trick though is in recognizing which links are unnatural.
ColourOfSpring...for your site that you removed all of your links I have a few thoughts. Did you download your links from WMT? If there were links that only Google could see then they would be in there. Is it possible that you had any sites redirecting to this one? If those sites had unnatural links then they could pass the penalty on. And thirdly, are you positive that the warning mentioned links? Sometimes Google can give penalties for on-page issues as well.