When you deleted a lot of backlinks, you site lost a lot of its incoming "pagerank juice". And google has probably devalued the shady backlinks you didn't delete, causing even more incoming "pagerank juice" to be lost. This lost "pagerank juice" had previously helped to boost your site's rankings, so without it your rankings have fallen.
This is why I said in another thread that most likely the only way for a site to make a "full" recovery from Penguin is acquire some new "natural" backlinks to replace the incoming "pagerank juice" that has been lost. I think this will still be true even if Google fixes the Penguin part of its algorithm to remove the penalization aspect of it.