I bought a song yesterday on Xbox Music (on the phone directly). The songs was downloaded and is present on my SD card. But it's not showing in XBox Music.
Today's update seems to have done the trick. It still didn't show in Artists but after I found it in the Albums section, it appeared in Artists as well.