It can be done but not by simply changing some settings.

First, you need to get the icons. Unless you have an icon creation program, you can use 32pixel square bmp files. You would create them and place them in a safe place, for example
C:\FolderIcons\red.bmp
C:\FolderIcons\blue.bmp
etc.

Create and name your new folder. Inside the folder, create a new text file. Open the text file and type two lines.

[.ShellClassInfo]
IconFile="C:\FolderIcons\red.bmp"

Obviously, you would use the correct path for the icon and folder you actually created. Save the changed text file, close it and rename it "desktop.ini". Change the file attribute of desktop.ini to "hidden". Change the attributes of the folder itself to "system". Refresh your desktop or reboot.

I have a script that automates the process for you but I can't find where I put my colored folder icons. If I have time later, I'll try to make some new ones.