Хотя в стандартном j2me нет способа сделать это (за исключением обновления, как писал omermuhammed), если вы ориентируетесь на телефоны, которые допускают нативную разработку (на ум приходят телефоны Symbian), вы можете зарегистрировать другой файл как значок мидлета или перезаписать существующий файл (запустив собственный код, а не Java) после установки мидлета.
Некоторые новые телефоны Sony-Ericsson (с платформой JP8.3 и выше) имеют собственный API-интерфейс управления приложениями java, доступ к которому можно получить только в том случае, если ваш мидлет подписан Sony-Ericsson, а также свойства jad, которые позволяют скрыть ваши Иконка мидлета от пользователя. Хотя я не думаю, что это действительно позволяет изменить значок, это может упростить автоматическое обновление.