以下のブログに詳細に書いてありますが、3.1以降は、ユーザがアプリを少なくとも1回起動しないと、broadcastなどは受信できないそうです。適当なActivityを追加して、1回 Launcherから起動すれば、次のリブートで正常に動くはずです。(自分は試していないですが)
http://commonsware.com/blog/2011/07/13/boot-completed-regression-confirmed.html