A challenge I'm facing in a brand new company is building contacts and gathering trusted customers. Specifically, how do I convince potential customers that we will provide the best quality of service?
Where do your customers hang out? Would you find them at local business networking group, do they have a forum online, are there linkedin groups, facebook groups where your prospects would be?
Wherever they are, that's where you need to start actively going (in the real world, or virtual) and start to have a presence. Don't go to sell, but educate them and position yourself as an expert.
If there are tradeshows, associations or anywhere you can do a presentation or speak about industry related topics it will help you do that as well.
People will buy from people they trust and who are the experts.
Start blogging, tweeting and putting information on the internet related to your business and expertise.
ULTIMATELY - what you are going to want to do is get great testimonials from your first customers. Written and in video to put on your website. This is one of the best ways to get others to be confident in your abilities.
I don't have the discipline to do it on every project :] but I get video and written testimonials whenever possible. Example: Testimonials
Also try to blog at least a couple times a month Blog
and I do an educational speaking engagement every couple months to a non-profit, chamber of commerce or somewhere and that always gets a couple leads.
You need to let your potential customers know you exist. Think about running advertisements in your local paper or take online ads. Also look at freelance project sites sometimes the job poster will not care if you are a individual or a business.