Well it definitely got worse before it got better, but I think I figured out a way to fix the problem. I'm still not sure why it happened, but as my phone continued loading the album, artist, and song lists from iCloud, it started mixing up the order in addition to not putting the right artist under the right letter header. By the time it was done, I had about a dozen "various artists" and several of the albums and artists had multiple entries on the list (all leading to the same list of songs).
Turning iTunes Match on and off didn't seem to help, so I thought I would take a more aggressive approach. I turned off iTunes Match and deleted all of the songs that were in my phone's memory (dragging to the right across each artist and pressing delete). After I deleted the songs, it still showed the iCloud logo next to the artist, so I had to turn iTunes Match on and off again to get it to show me that I had no music in my library. Then I turned iTunes Match on AGAIN, and upon going back to the music app, I was greeting with a new screen: an iCloud logo with a progress bar beneath it. It then downloaded all of my music and ordered things properly!
Now I am just in the process of downloading the songs I want again from iCloud. It was pretty annoying to have to do this, but it seems to be working very well now and the artwork is even syncing properly.
