I'm not behind my gentoo machine, so I can't check, but did you try running frozen-bubble from Konsole?

If that's not it, just look in /usr/bin or /usr/X11R6/bin for '*frozen*' or something like that. If frozen-bubble does not make an entry in the Kde menu, you can easily make one yourself with the menu editor (or put a link on your desktop, or on your panel, or whatever you want).
In general, you could check the output of emerge towards the end, where the package is being installed to your filesystem. Look for the lines starting with '>>>' and scan for /usr/bin or something like that. Good luck!