If someone is going to solve the music problem, the business model should be as focused on addressing the concerns of labels and artists as it is on consumers. If the middleman is making customers happy, and artist/labels feel like their getting an equitable fee, lock-in will happen and it will become a strategic disadvantage to leave.
It's far too easy to say "give the customers what they want. Your model is antiquated, catch up!" That isn't solving a problem. If we only look at the consumer end, we're bound to end up with lots of models that don't interest labels and artists, and ultimately will not satisfy customers either. If the ultimate destination is a world where we largely marginalize labels (which seems to be something a lot of people advocate as it will push costs down), then does Spotify get us any closer to that goal? Not as it stands now.