Replying for quick reference of Debian 8.2 users like me. There is a lot of info elsewhere, but a proper summary/solution should be collated here.
So, today, I've onfirmed the issue exists - and is due to baloo being configured in ~/.kde/share/baloofilerc to search /home/user by default - yet not being installed!
Dolphin checks this 'red herring' baloofilerc and hence tries to use baloo for searching /home/user - yet baloo does not exist - hence the "Invalid protocol" message.
There are two ways around this:
(A) fall back to filenamesearch by disabling indexing in baloofilerc - works but loses all benefit/availability of a properly indexed search
(B) aptitude install baloo. This resolves the problem, after allowing a few minutes for indexing to kick in, allowing nice modern search of /home/user
Additionally installing kde-config-baloo-advanced gives a proper UI to view/configure the preexisting baloofilerc and should be highly recommended to preserve the userfriendliness for which KDE is justifiably famous.
Summary: Debian 8.2 sets Dolphin to search /home with baloo - but omits to install the service to handle this. It also omits GUI config, meaning users diagnosing this need fairly advanced file knowledge. These should be installed by default. This remedies the default install being unable to search /home + lets the user configure indexing to taste.