Issues with full screen are hard to troubleshoot because they're so tied to your specific hardware. Here are some miscellaneous ideas:

• If you switch back to 8-bit color, does full screen work then?
• Do you get different results from switching color depth in the ingame video menu, rather than the dropdown video menu?
• Does deleting jazz2.cfg do anything?
• If you're comfortable using regedit, you can look for suspicious items in HKEY_CURRENT_USER\Software\Epic MegaGames\Jazz Jackrabbit 2\1.23 or HKEY_CURRENT_USER\Software\Epic MegaGames\Jazz Jackrabbit 2 Special Edition\1.24 depending on what version of JJ2 you're running. You could take screenshots of the data or even just try deleting the entire registry folders.
• You could try running UnInst.exe and then installing JJ2 again