I wonder if the phone is more complex to tear down, and more likely to be damaged in their process, making the cost of painting it prohibitive. It makes no sense to charge a hundred bucks to paint a phone if the customers are going to accuse the company of screwing it up and demand replacements that cost more than the service.
There are always cases. I really like the two-piece Incipio Silicrylic -- a hard plastic shell that snaps over a separate silicone skin. It doesn't add much bulk and works great.
http://assets2.crackberry.com/images...28/large/1.jpg