If you have the money, you should try advertising in places you feel that will bring you customers. But you probably knew that and don't have the money ;)
Well, having a partner that has some background on marketing would be good. Also, posting on hackernews and similar sites can give you a small boost shorterm. But you've obviously thought of that :P