For anyone else coming across this thread I had this issue and was pulling my hair out. I had the service declaration OUTSIDE of the '< application>' end tag DUH!
RIGHT:
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
...>
...
<application android:icon="@drawable/icon" android:label="@string/app_name">
<activity ...>
...
</activity>
<service android:name=".Service"/>
<receiver android:name=".Receiver">
<intent-filter>
...
</intent-filter>
</receiver>
</application>
<uses-permission android:name="..." />
WRONG but still compiles without errors:
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
...>
...
<application android:icon="@drawable/icon" android:label="@string/app_name">
<activity ...>
...
</activity>
</application>
<service android:name=".Service"/>
<receiver android:name=".Receiver">
<intent-filter>
...
</intent-filter>
</receiver>
<uses-permission android:name="..." />