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.

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 on natively on Xubuntu (it’s available in [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+)