I installed an echo Dot for My Aunt (For those who have followed my entries by my user name), With Zero help she can now control her Own Entertainment equipment now! It's Awesome... She was absolutely astonished and almost tearful with joy that she can now adjust her own volume, Change Channels, Turn the system on and off through Alexa. For a Quadriplegic, This is Almost like getting a new set of hands... that work. All this prefaces the next part...
On the Echo I have (full size tall boy), I get Music Stations, Songs by artist, songs by Genre... Singles if asked for a particular song... All of that... But on the Dot I installed for my Aunt, All I get is the same response the OP Mentioned, offering the Unlimited service for a fee... I will admit I already had Amazon Prime for a few days (couple of weeks maybe) before I got My Echo... I set hers up and opened an Amazon Account and added Amazon Prime (just like mine) all in a day. Is there maybe a delay in access once you set up Prime? or does the music stuff just not work the same on Dot?