This happens because from Android 3.1+
you Service will not run on Boot unless you start(launch) your Application atleast once after installation. So, when you install your Application and restart the device prior of launching the Applications MainActivity your BroadCastReceiver won't be fired. For that you have to launch your MainActivity once and then restart the device. That works!
For reference you can check my question here.