This is not "theoretically"; this is how it works.
The Legacy crew were at their cleared level. The Gol crew were at their cleared level.
Clearly, ATC thought the Legacy was at a different level.
"WHY?" will be the focus of the investigation. I hope. And as part of that investigation, the flight plans, communication difficulties, transponder failures, poor design of software and displays, and quite a few other things will come under the spotlight. I hope.
I would not want to work as a controller with equipment that gave such a poor indication that an element had failed, and as part of that, defaulted its display to a level I had not deliberately entered myself. (In this case, FL360.)
That it failed to work, in this case, is not a problem with the way aircraft are cleared, it is a problem with this particular combination of ATC, software, and probably a few other things, such as organization, training etc.
Given what I have read in this thread, the route and expected altitude change at a certain point wasn't the issue, here, it was a contributing factor. A big one, for sure, but still contributory. It could have happened anywhere there were two aircraft converging at the same level, one with a transponder out. I am sure there are places in Brazil where routes cross and aircraft at 89 degrees to each other can be at the same level, according to the quadrantal rule. (There sure are here.) In these cases the job of ATC is to ensure they will miss.
Of course, the chance of collision is greatly increased if they are both on the same or reciprocal tracks that are defined by GPS.
There is nothing in the clearance delivery or flight planning areas that authorizes a change to level, without direct communication with ATC at the time (or near the time) the change is requested.