kaled - 12:08 am on Feb 21, 2010 (gmt 0)

Is it just the start menu or do desktop icons behave similarly?

There is a registry setting that might possibly be faulty. Look in
HKEY_CLASSES_ROOT\lnkfile
There may be a key called DefaultIcon - if there is, rename it to something else, log off and log on again.

This key should not be present for lnkfile but if it were present it might possibly have the effect you have described. (NOTE : That's LNKFILE not INKFILE)

Kaled.