Android — Не работает protectionLevel="signature" в случае сервиса?

А вы запускали сервис со стороны клиента (startService или bindService)? Я точно не помню, но установка в вашем случае должна пройти успешно, а вот при реальном использовании компонента должна возникнуть ошибка.