This worked for us (Dropbox) too. Google's another example of this progression, though they also partnered with companies that already had big mainstream audiences.

Also, make it easy for existing users to invite new ones. Better still, design your product to be viral/users bring in other users as a natural consequence of using the product (e.g. PayPal, etc.) This sounds obvious but often isn't done well.