Marketing is essential and the biggest problem with most startups. And I'm a founder in a startup that suffered for a while from lack of new users.
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