How to stop Beautiful Widget from being removed on device reboot?
Make sure the app is on internal memory, not the SD card. I know that Android does not support widgets for apps that have been installed to the SD card instead of internal memory (at least for android 3 and below; not sure if it has changed for android 4).