This seems like it might be related to my switch to iTunes Match. My Music App displays the artists out of order. Other lists, like Songs and Albums, are sorted correctly. At the start of the list they are sorted correctly, after scrolling down a bit then the headers that separate the letters are in the wrong spot, and by the time I get to the bottom of the list they are no longer sorted correctly. Additionally "Various Artists" appears multiple times (10 - 15 times).
My iPhone 4 is out of warranty, so I can't log an online incident.