Congratulations on your launch!
My experience leads me to suggest a few things
1) Start your own double optin email newsletter subscriber list. While it will be slow at first, getting others to subscribe so you can email them regularly will be valuable down the road.
2) I would offer a no risk 30 day trial so people can evaluate it. I use Intuit Quickbase and they allow you to sign up and use it without entering a credit card for the first 30 days.
3) Buy advertising within other "quality" email newsletters sent by other small business websites. For example http://smallbiztrends.com/
has a newsletter they send out. Find out how can you advertise your "free trial" in their newsletter. Some of these newsletters have a large subscriber base. The bigger the better, but make sure the audience is small business targeted. I would subscribe to as many small business newsletters to get a feel for what they are sending. Then do some test advertising with a few newsletters that you think would be best.
4) Consider getting a tradeshow booth at some of the webmaster and search engine conferences. For example Search Marketing Expo, WebmasterWorld's Pubcon, Search Engine Strategies all have large audiences of webmasters/etc that have client bases that they could utilize the software with. Offer some sort of affiliate program for incentive. Can others whitelabel it also?
You will want to explore further tactics but that is where I would start.