This is really a great question. It's tough being isolated and tiny. At this stage you would rather be hated than ignored, but one even cares enough to hate you.<p>For your first users I think you have to do it "the hard way", by really _selling_ the product. Go manually find the low-hanging fruit for your product. Find the early adopters -- the people who will be delighted to learn your product exists and immediately understand its utility.<p>Bug all the people you know and get them to use your product where it makes sense.<p>
A little background: I'm the lead developer on a self-funded Web startup. It's a (mostly) free service to help musicians and bands stay in touch with their fans. I have a lot of confidence in it as a great product. What are some (cheap) ways I can make noise about it and get people using the site?
Go to concerts, offer drinks to the bands and talk about (read: sell) your product.
I don't know if it's efficient (I guess it probably is) but at least it's fun.<p>
How about emailing people at some of the popular ezines that are in your target demographic. They could post about it and you'd probably get a lot of traffic and artists interested in signing up.<p>I also agree that going to shows and introducing yourself to bands will help. Any personal interaction like that would get me to try out the service over a junk spam message on myspace.
The feature set you have put together might be very useful to some potential users who aren't bands. You might be in one of those "we built it thinking of market X but ended up filling a need for Y" sort of situations.