Developers, have a look at the REG files in this forum thread http://forum.team17.com//thread/41652/
Using the same parameters, optimize the files for Zelda Classic and you should no longer get corrupted colours 😊
I am not familiar with the parameters so I can't help any further then that. It fixes the display palette getting corrupt in Worms: Armageddon which is another old Direct Draw game so it should work for ZC.