From Android 3.1, newly installed apps are always put into a "stopped" state and the only way to move it out of the stopped state is to manually launch any Activity of the app at least once.
For your problem,
1) You need to design a mechanism where the user needs to first open any Activity of the app manually after installing the app.
2) After that, your BootReceiver will work correctly and it will be able to launch any Activity of that app automatically. Your implementation is absolutely correct.
I faced the same problem in one of my apps, where I was trying to open an Activity every time the device boots but it didn't work for a newly installed app. Once the user opens the app manually at least once, the app moves out of "stopped" state and everything works normally.
EDIT
1) Please ensure that the <uses-permission> is a direct child of the <manifest> tag.
2) Please ensure that you specify android:installLocation="internalOnly" otherwise you will not receive any Boot Complete actions if the app is installed in the SD card.
3) As I explained before also.