The General configuration tab of the installer project has a simple setting to specify the icon to be displayed.
This can either be an ICO file or an EXE that contains an icon resource.
The specified icon is converted into the file ARPPRODUCTICON.exe that gets installed into "C:\Windows\Installer\{
It turns out, that InstallShield doesn't like spaces in the ICO file name. Removed the spaces and normality was restored.