Yes. In this case, it makes an enormous difference. Your application can't just go to rdio/api/1/artist/whatever to look up the tracks for an artist; it has to make a SOAP-style request for the tracks for a given artist. This isn't a style nit.
Note: Requiring that the call are OAuth'ed, doesn't affect its RESTness.
I often think that, via REST APIs and content negotiations, API can become browseable and self-descriptive but I've yet to see any example of such a thing. Furthermore, just because an API is restful doesn't mean it's well-designed, and doesn't mean it has descriptive APIs (the artist's track could just as well be in rdio/api/64D89CAC?q=42, that wouldn't inherently make the API non-restful)
It should be trivial with AtomPub/GData/OData APIs. REST itself is not specific enough for that.