since your music that you had before, that came from your previously purchased albums is on yr device, it sounds to me that you are not even connected to Music at all and/or at least have not downloaded the songs from Music to yr device.
you can have lots of "music" on yr device that only amount to playlists that means you need to be connected to the net to listen to them.
once you download them to yr device you dont need to be connected to the net to listen to them.
every time you see the "+ " icon it means that it is basically only a playlist and NOT downloaded to ur device.
click the + to download that song.