I’m using Quod Libet with a music library of 170 GB (more than 30000 tracks).
Its performance is outstanding. My PC is old and has weak hardware, but listing/searching all those 30000 tracks only takes a few seconds (maybe 2-4 secs).
This good performance was one of the main reasons why I chose QL, but I’m very happy with all of its other features, too. It’s one of those rare pieces of software which I consider perfect for me, and I can recommend it whole-heartedly.
About your other requirements:
- it runs natively on Xubuntu (you can install it from Ubuntu’s packages)
- it’s gratis and Free/Open Source
- it uses GStreamer, so it can play MP3 (and all other file types you‘ve GStreamer plugins installed for)
- you can create/import/export playlists
- it’s not a KDE application (it’s based on GTK+)
It comes (nicely integrated) with the tag editor Ex Falso, which I’d also consider really good (I used it to organize all those 30000 tracks).