While not cheap, I ordered a custom Vaja leather case (which arrived monday, took over a month to make) and love it. I added a belt clip and had a special promo code (it's expired now) for $10 off. So in the end, it cost $75. Like I said, not cheap.
However, I absolutely love the thing. It's black with 2 blue racing stripes and fits like a glove. I've also got an invisible shield over the glass for further protection (it also reduces fingerprint marks).