From https://bugs.gentoo.org/show_bug.cgi?id=378123 FindMusicBrainz.cmake from kdelibs is broken because it doesn't set MUSICBRAINZ_FOUND variable at all - so NO musicbrainz support was ever compiled (on k3b or wherever else) after rewrite to KDE4 API (and thus after rewrite of buildsystem to cmake).
Thank you for the bug report. As this report hasn't seen any changes in 5 years or more, we ask if you can please confirm that the issue still persists. If this bug is no longer persisting or relevant please change the status to resolved.