Just to let you know, I had the symbol before I've done a hard reset (I've done it because Cortana did only Bing searches, but now its singing and everything , except the music recognition )
I find a way! You can ask her "what song is playing?" and she will start to listen to it. That means actually we don't need that music icon for her to name the song.
I found that the icon appeared after I changed the regional format to US. I had everything set to US, except this because of the date format. I had it set to Croatia, which is my home country. I also found out that it works with other regional formats eg. Germany, UK, Ireland, France, Italy, etc.
And when you ask her "what song is playing?" she'll start music recognition regardless of the regional format settings