Yes but what treaty? Was it the Klingon neutral zone? Which we never knew existed before Undiscovered Country or was it the Romulan neutral zone, with Klingon ships on patrol or was it more that the writers didn't know their stuff?
Where did you get the idea that the Klingon Neutral Zone didn't exist before TUC? Kirk has lines that are explicit in stating that the Kobayashi Maru deals with Klingons. "Klingons don't take prisoners" sure sounds like the writers knew what they were talking about to me. Any reference to treaty in that regard must at least imply the Organian treaty, at least to viewers familiar with earlier Trek.
The references in TWoK to the Gamma Hydra system, a neutral zone, and the no-prisoners policy were all elements found in “The Deadly Years”, an episode featuring Romulans. I’m sure there’s a logical explanation for replacing them with Klingons.
The Klingon footage that we see at the beginning of TWOK was of course recycled from the opening of TMP, so it was either going to be Klingons or, like "Elaan of Troyius," Romulans in Klingon ships. They probably just went with saying it was Klingons because it was simpler. No need to get convoluted in the opening scene of your movie.
In universe, I'd say that there either was a Klingon Neutral Zone, as they say there was in TUC, or else having Klingons suddenly appear in the Romulan Neutral Zone was a deliberate inconsistency introduced into that version of the
Kobayashi Maru test (Expect the unexpected!).
In my headcanon, there are multiple versions of the
Kobayashi Maru test anyway, all dealing with the basic mission of rescuing a ship by that name that ultimately proves to be a no-win scenario. That way the instructor can tailor the test to the various cadets taking it, and it makes it easier to keep the details secret amongst the cadets (After all, the SATs aren't the exact same test every year, are they?).
So the Starfleet Academy class of 2282 dealt with one version of the
Kobayashi Maru when they took the test on March 20th, and the class of 2283 dealt with a similar-but-not-identical scenario when they took the test on March 21st of the next year. Maybe Captain Spock let Admiral Kirk suggest a few elements into that day's scenario, and Kirk threw in some Klingons to mix things up.