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.

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.