Eso pasa, como te han dicho, con las aplicaciones que están en la tarjeta, no en el teléfono. Al reiniciar el teléfono pierdes el icono de acceso directo en el escritorio.
A título personal te recomiendo que muevas todas las aplis al teléfono, evitarás que te ocurra eso, y dejes la tarjeta para multimedia: fotos, musica, videos....