Parece mas bien fallo de tu sd por lo que comentas...
Yo tengo las aplicaciones instaladas en la sd y no tengo problemas de ningun tipo ya sea reinciando el movil o apagandolo y encendiendolo...
Prueba a cambiar la sd o a pasarlas a la memoria interna (lo más logico)