I'm trying to add a DTS CD that was seemingly released in 1995: https://www.discogs.com/release/11039227-Various-Surround-Sound-For-The-Millennium
but am getting the "This medium is set to a format that did not exist on the selected release date" error.

In fact the format documentation page says DTS CDs were created in 1992: https://musicbrainz.org/doc/Release/Format

On the other hand, this Billboard review mentions them existing "since 1996": https://books.google.com/books?id=GCkEAAAAMBAJ&pg=PA18#v=onepage&q&f=false

Regardless, either the format or the documentation (or both) needs to be corrected. My sense is that the Billboard review is wrong, because there would be no reason for this release to exist in a non-surround form, so it's unlikely to be a case of the copyright date being significantly earlier than the release date.

That said, I'm not sure 1992 is correct either - my guess is it's extrapolated from the creation date of the codec, not necessarily the physical format of the DTS CD (i.e., DTS encoded as S/PDIF PCM on an audio CD). Wikipedia mentions that Jurassic Park was the first film to use DTS, in 1993, using a CD-ROM, which would likely have preceded the DTS CD. https://en.wikipedia.org/wiki/DTS,_Inc.#History

Looking on Discogs, this appears to be the earliest DTS CD - there's an entry there for a Lyle Lovett album, but I think that's based on its copyright date and it's actually an undated reissue from a few years later. https://www.discogs.com/search?q=dts&type=release&format_exact=CD&sort=year%2Casc&page=1&format_exact=Multichannel