Users can still change the desktop background color in Windows Server 2012. Note that you need to have Desktop Experience installed. You also have to allow users to change their colors and desktop background in Group Policy.
The way I did this was:
Open Control Panel. Under Appearance and Personalization, choose Change desktop background.
Choose the drop-down next to Picture location (which is confusing) and change it to Solid colors.
You can select some existing colors.
Or, click More at the bottom left, and you can select a custom color.
Voila! Now my desktop is UGLY, just the way I like it!
Or you can select some other folder with Browse if you want to select a background image from somewhere as a wallpaper.
However, this doesn't complete the picture. As you can see, when I set a solid background color, the taskbar changed but my window borders didn't change. I suspect this is a bug.
To actually override the color of the window decorations (and taskbar) do this:
Open Control Panel. Under Appearance and Personalization, choose Change the theme.
Near the bottom center, choose Color to change the color.
The first tile is Automatic and Windows will derive the colors from the desktop background wallpaper. (Assuming all the bugs are fixed.) Selecting any other tile will allow customization.
I think these are about the only real options users are going to have.