But still, they want to see serious progress within a month (eg. large number of bug fixes).

You need to sit down with them and explain that just isn't possible, then explain clearly what is possible, and what the options are (painful rewrite in parallel to maintaining the old software, or painful and slow refactoring), and just how much it's going to cost them. They aren't going to like either option but it's better for them to understand upfront exactly how much of a problem they have, and that the problem was not necessarily with the previous contracting companies, but with their codebase.