The icon was in the resource file, yes.
I resolved the problem. First, Installing the icon plugin (\imageformats\qico4.dll) on the target machine solved the problem with ICO files. Secondly, using a PNG icon does not require a plugin at all.
Useful documentation can be found at: http://doc.qt.nokia.com/4.7/deployment-plugins.html
Thanks for the help!
Leo.