http://developer.android.com/reference/android/app/Service.html#startForeground(int, android.app.Notification)

Без этого сервис рано или поздно будет прибит системой. Так что сервис обязательно надо делать форграундным, если нужно чтобы он постоянно работал в фоне. Я здесь уже выкладывал ic, который это реализует. Правда по-минимуму. Можно еще реакцию на нажатие на уведомление сделать и смену текста в уведомлении. В ic надо сменить package на свой и, возможно, "service1" и "ic" в 2 местах. ic размещать внутри сервиса.