Oh, yes it does
recordmydesktop does have a GUI frontend. It's called, unsurprisingly, gtk-recordmydesktop and is available through synaptic on a default install.
If the OP wants a start menu item, he shalt have one by installing gtk-recordmydesktop using synaptic. The menu item appears under the sound & video menu.