Using Speed Effect Makes Video Quality Very Bad

I did some destkop recording. Mostly me writing PHP code. The recordings are looking perfect.

However if I insert them into a KDEnlive project AND I apply a speed effect of let's say 130% on a clip, that clip will become very poor quality. So bad that text is almost impossible to read.

I came across this 2 years old thread: http://www.kdenlive.org/mantis/view.php?id=1831 but it does not really help much. I tried to record my screencasts or transcode the recorded OggTheora ones into mpeg4, mpeg2 with different options like:

avconv -f x11grab -show_region 1 -video_size hd720 -framerate 24 -i :0.0 -threads 2 -flags2 local_header -q 1 -g 0 -vcodec mpeg4 ./test.mp4

or

avconv -show_region 1 -f x11grab -s 1280x720 -r 24 -i :0.0 -threads 2 -vcodec x264 -q 1 ./test.mkv

or even mpeg2.

With all the options I have the same, or even worse, video degradation.

Can someone please tell me how should I record or transcode my videos so that I can apply a speed effect without quality loss?

PS: in case someone doesn't know it, avconv is just the new ffmpeg.