If it's any consolation, you're not the only person who has suffered this problem. Several Xbox owners also have had problems with their Dark Souls games. The remedy they all offered is the same as what you've done - formatting the HD. Except that in other cases it seems to have worked for them. I also went to our local retailer and some other shops yesterday explaining you problem, but they also said the same thing, factoring out the possibility of a defective game. Either way, they said that the only way to know for sure would be to inspect the unit.
Anyway, how's your new game copy working with your new console? I'm assuming everything's working now?