I've made some progress on the original problem:

If I scroll up and down in the "Browse Artist" menu on the player, I can see that all my artists are listed. But for some reason they're in 2 groups:

1 of 3828 10cc
38 of 3828 A.D.A.M
3599 of 3828 ZZ Top
3600 of 3828 5th Order
3602 of 3828 Aalacho
3828 of 3828 Zappacosta

Now here's the annoying bit - the player interface and web interface shortcuts jump straight to the second group of artists, completely bypassing the first group.

For example, in the player interface, if I jump to "A" by pressing 2 on the remote, it takes me to Aalacho. The only way to get to ZZ Top is to jump to Aalacho and then scroll up.

The web interface is even worse - there seems to be absolutely no way to browse to the first group of artists! Clicking "Z" lists Zappacosta, but ZZ Top is nowhere to be found.

As I explained before, the problem doesn't exist in 7.3 - it was introduced during the SQLite changes in 7.4. Once 7.4 reverted to MySQL, the first nightly worked perfectly again. But the second nightly failed, so its something to do with the SQLite changes that were merged back to the trunk.

Hopefully this explains the problem a bit better!