With id3 genre tags in particular, I noticed that the e140 seems to cache them in an unreliable way. I had some bad / incorrect tags in some of my mp3's, and when I'd update them and restart the e140 the old values would still be there.
The solution I found was that if I renamed the files, the e140 would pick up the new values. It's easy to batch-rename them if you're using a decent tagger (I personally just went from "00 - title.mp3" to "00 - artist - title.mp3"). I'd try getting all of your tags correct, then renaming all your mp3s so you're sure the e140 reads all the new tags. If it works, you can then rename them back to the format you prefer (if you're particular about that).