I’m using [**Quod Libet**](http://code.google.com/p/quodlibet/) 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](http://packages.ubuntu.com/trusty/quodlibet))
* 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).