@brycebaird
Sorry to hear about the troubles you have. Don't yell at me now: Have you consistently named your music and mp3 tags? this is important. For example if you name an artist 'ELVIS PRESLEY' but then for another track 'Elvis Presley' PP will recognize this as two different ones.
I had added so much music recently that I decided on a rainy Sunday to disconnect the HD I am using and hooked it up directly to my computer. I then deleted the file .cedata which is the large index PP builds when you connect a drive to PP. For my music I use a freeware program which is called 'MP3-Tag' (http://www.mp3tag.de/en/ )which builds and maintains a database of all your music. With the HD attached to my computer, I corrected all wrong information and filled any gaps (like e.g. album artist, genre etc. etc.). This took me quite a long time but Elvis is now Elvis and not ELVIS. The software can also search for album covers which I did and if I just could not find the one I was looking for I pasted a jpeg in. When I was done I reconnected the drive to PP and it started indexing again which probably took some hours. I would not know because I did this late in the evening but the next morning it was done.
Opened up the 'Jukebox' and 98% (there is still some inconsistency - my fault) but in general it works fantastic. I can list by artist, by album or by genre. For example I click on genre, then on 'Jazz' and all the albums I tagged as Jazz are showing up. I see all album covers, all song title are displayed etc. I am very pleased with this. The only drop of bitterness is that I can enjoy this as the PP owner but for the people I share my music with the jukebox function is not there. I think CE have to open this also for sharees. Don't know if this helps you at all but I can assure you it works great for me.