Despues de cambiar el icono en Project -> Options -> Application -> Icon le das a Project -> Build ... Para que delphi vuleva a crear el ejecutable con el nuevo icono.
Si aun asi sigue sin cambiarlo probemos a lo bruto
En la carpeta donde tienes guardado el projecto tiene que haber un archivo con el mismo nombre que tu projecto pero con la extension .res, ahi es donde se guarda el icono de la aplicacion, prueba a borrarlo (o mejor cambiale el nombe) e intenta abrir el projecto, delphi te informara de que no encuentra el archivo y creara uno nuevo con el icono por defecto