Something to consider once XenForo goes gold.
Developing a Wordpress Theme (the right way) takes 100s of hours and at this stage is simply not possible for us.
We are focusing 100% on building our Xeno Framework that will be powering all of our styles.
http://xenstyles.com/ is a great site for custom high quality styles and I know with john being the ex-owner of vbskinworks his support, and style updates where and still are excellent.
Themesinc - miko's site will be another great high quality style provider.
Completevb who styled http://forums.wtf.com/ seems to be good judging by the work they did at wtf.com. I don't know what their support is like, or how quickly they update their styles but the work seems to be of high quality.
I also know Dragonfly (kim) is working on styles and almost sure she provides a custom service. She's an ex ipb styler and in my books was the best ipb styler with stunning style releases. http://www.xenique.com/forums/index.php
If your willing to pay these are the people who I would recommend. Most 3rd party sites not dedicated to styling usually do re-coloured jobs so quality is compromised, and updating them isn't their highest priority which is something you ought to bare in mind. If it's high quality styles your wanting the list above would be a good start.
Thanks for giving me a good idea. I'll try recoloring too.
I am hoping Hanafi Jamil aka napy8gen at http://sultantheme.com will change his mind and start skinning for XenForo soon. He has by far the largest and the most affordable selection of commercial vBulletin skins.