A maneira mais rápida seria deixar seus ícones de inicialização como estão e colocar um link simbólico no lugar do seu antigo programa que aponta para o novo local:
mkdir -p /original/directory/of/program/executable
ln -s /new/path/to/executable /original/directory/of/program/executable
Por exemplo, se o executável estava originalmente em /foo/bar/baz e você o movesse para /quux/blah/baz , você deve fazer:
mkdir -p /foo/bar
ln -s /quux/blah/baz /foo/bar