Hmmm..? It works for me without a problem. Tested it on two computers with different icons. What kind of icons are you using? The default size ot the icons in the right side of the start menu is 24x24, so best if the icon contains this size, should however also work with standard sizes, at least it should not make them unrecognizable.
You did put the path to your icon in quotes? (Important if there are spaces in it.)
Could one of you perhaps post a screenshot how it looks for you? I'm curious now what might cause this problem.