Hola. tenia el mismo problema y lo he solucionado. como seguro que habrá mucha gente a la que le ocurra lo mismo ( cambio de posicion de lugar de los iconos al reiniciar el terminal o que desaparen los accesos directos que se han editado de la parte inferior de la pantalla) os dejo la solución, que es tan sencilla como hacerle wipe al telefono y despues, para asegurarse, restablecer los ajustes de fábtica desde el propio menu del teléfono. Así los icono dejarán de cambiarse de sitio cuando les da la gana.
Me imagino que el fallo ocurrirá por no haber restaurado los ajustes despues de una actualización, el caso es que esto me ha funcionado en el galaxy s2.
Saludos