Anybody having trouble with Windows 8 Consumer Preview, do the following:
Open the Zelda Classic folder.
Right click zelda-w.exe and click Properties.
Click the compatibility tab.
Check "Reduced Color Mode" and set it to "8-bit (256) color."