It seems like tags might be a better solution to classifying music than over-broad categories like "rock".

Very much so; I've lost count of the number of times I've wished that players would recognize more than one genre tag; heck, even allmusic.com had multiple "styles" for their listings.

Of course, the real problem is human language, it's subtleties, and how people (ab)use it.