That would work if the *random country* government only owed money to other *random country government* but when they say Greece owes 40 billions euros to France it means they owe 40 billions euros to French entities, not necessarily to the French government (though some of that debt might have been bought up by the French government so for that part it would work).
It would be an improvement in that instead of having France owing 185 billion euros to British entities and Britain owing 194 billion euros to French entities you would have France owe 185 billion euros to French entities and Britain owe 9 billion euros to French entities and 185 billion euros to british entities but it would not make most of the debt disappear, it would just go one step towards removing much of the domino effect that can crash the whole European (and worldwide as we are connected to US banks) economy simply by crashing a small portion of it.
But just doing that would not be enough because besides the debt there is the much bigger problem of CDS's. CDS's, or Credit Default Swap are basically a bet that an entity (a bank or a country) wil go bankrupt. If I have greek bonds worth 10 millions euros and believe Greece will go bankrupt I can buy a CDS from another entity who believes Greece won't default (good luck finding good prices on Greek CDS's today though). If Greece does default that other entity has to pay me the 10 millions euros. Of course I paid them less than that to buy the CDS, so I do not lose as much as if I had no CDS... at least in theory.
You might wonder why I call them bets and not insurance. After all, if I think my house might get hit by a tornado I can buy insurance from an entity for the value of my house at a much smaller price than the value of my house. The reason I didn't is that insurance is a regulated market so if I buy an insurance I have a reasonable assurance that the entity has the funds to pay me (has enough capital to cover its liabilities). It's not perfect because regulators can fuck up (or be captured) but there is at least an attempt at due diligence. Also, I cannot profit because of insurance; if I insure my house twice, each insurance company is only liable for half of the value, I cannot get twice my house's value by buying two insurance policies.
As you might have guesses, CDS's are not regulated so not only can you have a CDS on the plus side of your balance sheet that is practically worth bupkis because your counterparty wrote too many CDS's and does not have the capital to honor all of them (hello AIG) and having the entity against which you took the CDS default would cause the entity from which you bough the CDS default too which would affect your balance sheet and could thus cause you to default... yep, another domino effect.
There is also the problem that you can have a million in greek debt but CDs's with a value of 10 millions, the equivalent of insuring your house twice (or 10 times in this example), and because there is no regulation you can collect (or at least try to, see preceding paragraph) on the whole 10 millions. So the 83 billion euros Greece debt problem could be hiding a 830 billion euros Greek CDS problem. How much more CDS's are there than government debt? We don't know because they are not regulated.