Have you decided on a new theme yet Yokoi? As much fun as I'm having giving Jones a hard time over the PM's, I'd feel much more important giving people advice on skinning.
If you're still considering a game skin, I'd say your best bet is an NES or SNES game, because any older and it'll be too ugly for the general population to not tend to find it ugly, and any newer games tend to have graphics too fancy to work with... The easiest game skins are the old-school games that had a solid black background, in my experience. But it all depends on what sort of skin you're looking to make.