Pues a mi no me pasa. Entro en aplicaciones pongo editar y arrastro el icono que quiero hasta el acceso. En teoria no tenia que cambiarte nada al reiniciar.
Ami me paso algo similar con las aplicaciones que ponia en carpetas que se salian de ellas al reiniciar. Borrando la cahe del launcher lo solucione.