VLC, Skype, Clementine and Virtualbox (the four QT apps I use) all have icons in their menus. The rest of my system's menus are all iconless, How I like them.
I'm using 12.04.
Icons in the menus is standard for Qt/KDE apps. In order for Qt apps to obey the gconf settings, the developers have to specifically code that in. You have no control over this, but it's not a bug in Ubuntu. It's behaviour by design from the app