Are the widgets/live wallpapers "Paid" apps, or Free apps?
Because there's a bug in 4.1.1 where paid apps don't get loaded at boot time, and it probably affects widgets, too. I have to deal with it with Swiftkey, where every time I reboot it's no longer selected as my default keyboard app. So after every reboot, I have to re-enable it and re-select it as my default keyboard.
May be the same bug is affecting your widgets.