I looked a little into the specifications and found that …
recordMyDesktop produces files using only open formats. These are theora for video and vorbis for audio, using the ogg container.
So, it's very likely that OpenShot has troubles parsing that container or either of these codecs. I would try and report a bug with OpenShot nonetheless, but if you want to try another container or video/audio codecs, you might succeed in parsing the videos without synchronization issues.
OpenShot uses FFmpeg's libraries for decoding, so chances are high it'll be able to parse anything you encoded using FFmpeg itself.
Your requirement was for the conversion to be lossless. This leaves two options:
Change the container and keep the codecs, e.g. from OGV to MKV. I believe MKV is the only container that accepts both codecs you have.
If you install a recent copy of FFmpeg (e.g. using a static build from here) — and please don't use the outdated version Ubuntu provides — then all you need to do is:
ffmpeg -i input.ogv -c copy output.mkv
Maybe that solves a problem related to OGV in OpenShot.
Transcode the video and audio streams to lossless codecs, e.g. from Theora to lossless h.264 video and Vorbis to PCM audio.
Again, using FFmpeg, this would be the following for lossless h.264 and PCM audio to a MKV container. Note that h.264 usually is not lossless, but
-qp 0 will achieve that:
ffmpeg -i input.ogv -c:v libx264 -qp 0 -c:a pcm_s16le out.mkv
Or, using an MP4 container, which doesn't support PCM audio out of the box. We'll need to re-encode audio to AAC here and supply a little higher bitrate so as not to reduce quality too much:
ffmpeg -i input.ogv -c:v libx264 -qp 0 -c:a aac -strict -2 -b:a 192k out.mp4
Hopefully, that'll solve your issues. If not, filing a bug report with OpenShot would probably be the best solution.
If you get confused by the termini used here, please check out the following question: What is a Codec (e.g. DivX?), and how does it differ from a File Format (e.g. MPG)?, and for FFmpeg usage, read our related blog entry.