Developers, have a look at the REG files in this forum thread http://forum.team17.com/showthread.php?t=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.