Just replaced the vinyl with a leather cover bought on ebay for about $20. Color match wasn't perfect (a warmer shade of gray), but close enough.
To replace:
1. Remove four screws holding underside cover of the console lid in place, and pry the cover off gently.
2. Remove four screws attaching the lid to the console hinges and remove the console lid.
3. Remove two screws attaching console lid latch and remove the latch.
4. Remove the numerous staples holding the vinyl on to the console lid using a small screwdriver, staple remover, or putty knife.
5. Gently peel away the vinyl from the console cover foam, being careful to not damage the foam (mine peeled off quite easily).
6. Place the leather cover over the console lid, making sure it's on in the correct direction—one end has a more pronounced curve—and align the cover so that the seams align with the edges of the console lid.
7. Staple the leather cover to the console lid, beginning at the center of the sides with the seams, working your way from the center outwards, being sure the seams align with the edges. Keep staples away from edge so that they don't show once you replace the underside lid cover. I used an Arrow T50 stapler with 1/4" heavy duty staples. A pneumatic upholstery stapler with an extended nose would have worked better at getting in the tight spaces on the lid.
8. Trim any excess leather away with a sharp utility or Exacto knife, or single edged razor blade.
9. Reassemble the lid and attach it to the console in the reverse order you removed it.
Total time: 45 minutes to an hour.
Someone else suggested taking the leather cover and console lid to an upholstery shop and have them attach it. I would probably do this if I didn't have the tools, the gumption, the patience, the time, or the skill necessary to do the job. Think they said they paid $20. So, for between $20–$60, you can have a console cover that's better than the original and cheaper than the cost of a new one.