You may need to be more specific about which icons.
Is it only shortcuts?
Get him to rightclick the icons and see what the Properties indicates.
The General tab will show a .LNK extension if a shortcut.
Does he have Win98?
(The fix may be different if not)

If it is only .LNK files, then try this:

I will give you a fix for the usual lnkfile problem
Make a file from the lines below called Link.reg and doubleclick it.
You can use Notepad to create it from this message. Don't retype it as
an error might occur. Copy it.
Ensure that REGEDIT4 is the first line and that your mail/newsreader
does not add a space to the end of any line.
Ensure the last line is blank.
If your Windows folder is other than C:\Windows then alter the file
accordingly.

You will need to restart Windows after this fix to see the effect.

----------Link.reg ----below this line
REGEDIT4

[HKEY_CLASSES_ROOT\.lnk]
@="lnkfile"

[HKEY_CLASSES_ROOT\.lnk\ShellNew]
"Command"="C:\\WINDOWS\\rundll32.exe AppWiz.Cpl,NewLinkHere %1"

[HKEY_CLASSES_ROOT\lnkfile]
@="Shortcut"
"EditFlags"=hex:01,00,00,00
"IsShortcut"=""
"NeverShowExt"=""

[HKEY_CLASSES_ROOT\lnkfile\CLSID]
@="{00021401-0000-0000-C000-000000000046}"

[HKEY_CLASSES_ROOT\lnkfile\shellex]

[HKEY_CLASSES_ROOT\lnkfile\shellex\IconHandler]
@="{00021401-0000-0000-C000-000000000046}"

[HKEY_CLASSES_ROOT\lnkfile\shellex\DropHandler]
@="{00021401-0000-0000-C000-000000000046}"

[HKEY_CLASSES_ROOT\lnkfile\shellex\ContextMenuHandlers]

[HKEY_CLASSES_ROOT\lnkfile\shellex\ContextMenuHandlers\{00021401-0000-0000-C000-000000000046}]
@=""

--------(end of link.reg-----
Note:
If you have the IE4 desktop update installed, or if you are using
Windows 98, then that line in the reg file should have a %2, not a %1.

[HKEY_CLASSES_ROOT\.lnk\ShellNew]
"Command"="C:\\WINDOWS\\rundll32.exe AppWiz.Cpl,NewLinkHere %2"

...Alan