I don’t know quite how the gnome menu is like, but in KDE your problem would suggest that the command specified by default is wrong. Maybe it points to the wrong location or have some parameters to it, that doesn’t work. Just look in the menu-editor for the path or command, you don’t have to have it to run in terminal.
Well I thins that maybe
/opt/kde3/bin/k3b is not in the PATH variable,
but I dont know where to add it.
Got another problem, when installing few programs zypper quits before completition, and leaving one or two programs not installed. I get no error warning.