I'm going to guess it appears when you have a certain number of artists. I have only a few currently and it doesn't have it.
I agree. For me no letters in artist view when accessing music stored on the iphone, but if I turn show all music on through iTunes Match then the letters appear.
It seems like it does depend on the number of different artists.