I've had my BS5 for about a year and a half, and, for me, it has been great. I rarely use my BS9000 any more. I think most of the "complaints" on this forum about the BS5 are not from owners, but rather from people who wish the product was something it is not (video server, touch screen, support for Apple lossless or Apple iTunes with DRM, etc.). At least one user on the forum bought one and returned it because he couldn't warm up to the interface, but most seem to like the interface just fine (I do). My general advice about the product is that if you are very particular about building playlists and playing a specific song at a specific time, then you'll probably be disappointed. Or put another way, if you must have the search/organizational capabilities of a computer program, this is not it. Personally, I don't want a computer (or computer type interface) in my lounge, and I enjoy spinning the wheel even if it is not the most efficient means to find a specific song. There is serendipity in spinning the wheel - I often find another song I'd rather hear before I find the song I set out to hear. The beauty, to me, is that it mostly plays a wide variety of music I like with minimal input from me - MOTS works as advertised - it's not perfect (long songs > ~20 minutes aren't analyzed, sometimes it seems to play a few songs a bit too much), but I think it works very well.
Apple support is not great. There is a program to transfer songs from MacOS to BM5 that works fine, but the Apple lossless format is not supported. FLAC is supported, but is not 100% gapless (the gaps are not nearly as bad as MP3, and, I have to listen very closely to hear the the gap, but it can be heard on some song transitions). WMA is the only gapless, lossless format supported at this time. I'm also not sure how one would edit tags, etc. once songs are loaded (sometimes you need to edit the genre, artist, album, etc.), but there might be a way - I have a mixed Apple/Windows home so I tend to use Windows for this task. This also goes to your experience about nothing under genre and artist being messy - the interface only knows what it has been told, via file tags. Keep your tags in order, and I think it works great. Messy, incomplete tags lead to a messy incomplete interface experience.
There is no customization of the navigation. I don't even see a "Genre" selection, at least not on the BS5 - I think it is there when accessing via TV and definitely there from BeoPlayer, but, again, no customization - it's the B&O way or no way. On BeoPlayer (so I assume the TV interface works the same), you do get exactly the navigation tree you suggest.
There are iPad apps, but I'm not using any... I will probably buy the Beo6 remote which just recently added 2-way, graphical interaction with the BS5. I also think the ripper is a great device, and will probably get one of these as well. Again, the less computer involvement the better (for me - I work with computers 8-10 hrs a day so this is why I don't need to see them when I relax with my music). Also, it will allow the wife and kids to add their own music without my help. Right now, I must first fire up my laptop, fire up BeoPlay, rip the CD... not hard, but the ripper should be an improvement for the instant gratification set. Then again, if you rarely buy CDs, then it probably wouldn't add much.
For me, I'd buy it. In fact, I already did and have been very pleased with it so far...
Stan