I had two different bikes bead blasted at Marco in North Minneapolis, then took the frames west of the cities to TC & J Powder coating in Rockford, MN. You can find TC & J if you Google them.
The bead blasting cost $30 per bike
The powder coating cost $30 per bike
Please note that Travis was super nice to deal with, but he did not have a huge selection of colors at the price above. You could pay more and special order a custom color though.
Here's my photo stream.
http://www.flickr.com/photos/41859388@N00/