Comment 4 for bug 108746

Sam, your package does install gnome-icon-theme-gperfection2 as a dependency, but unfortunately this does not appear to have any effect. Efax-gtk's menu entry in kubuntu's kde menu (under "Office") still does not have an icon.

You might want to take a look at bug #108742 which is very similar (but for a different package); it has detailed comments and recommendations by a mentor. From what I understand of it all is that the approach taken there is adding an icon to the specific package and changing the desktop file to point to that icon. Hope this helps you in your efforts.