I have done numerous custom designs - but it tends to be time consuming, with the slicing and dicing (e.g.,
http://www.takeajourney.org,
http://www.antiochchurch.cc and
http://www.restorechurchandhome.org) - $1000 - $1500 for the custom look work.
I have also taken some nice templates and tweeked them for the churches' needs (e.g., with
http://www.saintfrancisumc.org, I started with a template from youtheme.com) - still somewhat expensive depending on how much you want it changed.
Some places where I have found some nice templates are youtheme.com and joomlashack.com.
We are in the process of developing some new templates focused on churches, but are still 6-12 months from being ready to launch - we're still reengineering our own site (the cobbler's son has no shoes syndrome).
I'd be happy to discuss ideas/solutions with you - even if my company is not the right fit.
Mark Faggion - owner, GraceStream -
http://www.gracestream.com