You appear to be assuming that getting those licenses is difficult. It really isn't. If Spotify managed it, any competent competitor can also do it -- after all, the labels have no particular loyalty to a small Swedish online radio network.
Spotify is far from a small Swedish online radio network; here in Europe they are far and away the market leader. They have over a million accounts in Norway alone, which is phenomenal penetration in a country of 5 million.
Second, getting those licenses was incredibly difficult for them; the negotiations to enter the US market took several years. There is absolutely no indication that the record labels are prepared to give similar terms, or even any terms at all, to other competitors. Again, here in Europe, I know of several firms attempting to compete with Spotify, and they are getting hung up on precisely this point.