Make:

Back up your old settings
All of the localization text and icon images used in Front Row are stored inside the /System/Library/CoreServices/Front Row package. You're probably going to make a lot of changes before you settle on the theme you like. Heck, you may decide Apple's designers were on to a good thing in the first place. Either way, you'll want to copy this package to a safe place before you continue, just in case you want to revert your changes at some point.

Change Front Row's icons
Right click on the Front Row package and select "Show Package Contents." Inside, you'll find some interesting things in Contents/Resources. There are a bunch of PNG images in there for everything from the player control icons to the "Videos" and "Music" icons that rotate on the main menu.

You can open these PNGs in Gimp or Photoshop and change them to whatever you like. I decided to make a black and white sketch theme by running a couple photoshop filters on the existing icon set. Whatever you choose to do, I'd recommend keeping the same image dimensions as the original file. Also pay attention to the positioning of the icons so that your versions will be positioned correctly in the Front Row interface.

You can't directly save back to the Resources folder due to security permissions, so save all of your new images to a new folder on your desktop. The original format of the images is 8bit PNG. Save your new images in this same format.

Move your new icons to the Front Row package
You'll need to be root to replace the files in the Front Row package. So open up a new terminal and type "sudo bash" and enter your password. Then, change to the destination directory:
# sudo bash
We trust you have received the usual lecture from the local System
Administrator. It usually boils down to these three things:

Password: ***************

# cd /System/Library/CoreServices/Front\ Row.app/Contents/Resources/

Now copy the new files there. Let's assume you placed them in a folder called FrontRowTheme on your desktop:
# cp ~/Desktop/FrontRowTheme/*.png .

Now at this point, your probably ran Front Row and nothing appears to have changed. You need to restart Front Row for the changes to take effect.

Restart Front Row
By restart, I mean kill. It'll get launched again automatically when you try and access it. You can either reboot your machine or use ps to find the process id and then kill -9 it:
# ps aux | grep Fro
yourmac 5895 0.0 1.2 225920 12436 ....
# kill -9 5895

Check it out
If you run Front Row now, you'll see your new skin. Though it's a pretty simple hack, it's also a really nice way to customize the look of your machine.

If you want to go a little further, you can also change the text that's used within the program. Take a peek in the English.lproj (or the appropriate language) folder. You can open the Localizable.strings file in TextEdit and tweak the language to fit your style. Just save to your desktop and copy it back as root as you did with the images.

Have fun, and if you come up with a seriously awesome theme, zip it up and send us a url in the comments.