My partner and I have been working hard on HealPay.
After researching other billing applications, like FreshBooks, we think Invoicing should be free. We are excited to launch additional features pending Hacker News feedback :]
View the app at http://www.healpay.com
Invoicing is an interesting domain because your users are receiving money as a result of your service-- thus charging a fee only means slightly less money coming in (so cognitively it's treated as a smaller gain than an actual loss).
My suggestion would be to offer a free account that gives a taste of your service but leaves your users wanting more. FreshBooks is a good example-- you can only have three clients before you need to pay. Other options might be only paying if an invoice is above a certain amount.
Finally, a huge reason I use FreshBooks over email or my previous company's proprietary system is because I can give my clients a clean, professional interface where they can log in, view their invoice, and pay it online. So integration with Authorize.net, Google Checkout, (and I suppose PayPal, though I dislike them) are key. One thing you can do right away that is a step above FreshBooks is to allow authenticating against an external url using a REST API. This would allow me to give my clients ONE password to use on their sites as well as for billing.
Hope that helps.