Is there an easy way to edit gtk-recordMyDesktop videos?

You need to convert them first... they never worked without converting (at least for me):

mencoder -idx out.ogv -o out.avi -oac mp3lame -ovc lavc

Then you can edit them in your favourite video editor (I for one prefer Avidemux).

I see you had trouble with ffmpeg, but I have had a lot of good luck converting just about anything using it. If you don't specify a bitrate or quality setting in ffmpeg, it can use some really low quality settings. This may be why your conversions look so crummy. The video editors are picky about what kinds of videos they work well with, so I always convert to MP4 with MPEG4 video and FAAC audio. The command I use is:

ffmpeg -i in.ogv -vcodec mpeg4 -acodec libfaac -sameq out.mp4

The -sameq option tells ffmpeg to try to make the resulting video approximately as good looking as the original.

Once you have it in MP4, I recommend you use OpenShot to edit it.