Okay, this color glitch is nothing related with computers or windows, but just a compatibility problem between latest versions of Dosbox and Lemmings. This bug appeared in the 0.70 (or 0.71?) version of Dosbox. I did some tests trying to solve the problem and finally comes with a conclusion. The problem is... the mouse. It sounds strange, but true.
When you're on the main screen. Press F1 key to start the game and immediately after, click with the left mouse button (here, it depends of which version you have. If the main screen DOES a fade out, it's ok, but if it DOESN'T (turns black straightly), then it won't work). The messed up colors will disappear (if not, try again by entering the level and going back to the main menu), but you'll only be able to click on one of the mouse buttons (keyboard won't work). If you do, the messed up colors will show again and then, you'll be able to use back keybord and mouse and start the level by clicking on the left mouse button. Strange, huh?
As for recording, Dosbox already allows to record (from 0.65 version). Press CTRL+ALT+F5 to start and stop recording as an AVI file. You don't need Fraps for that.