is 720x640 really the size of your screen i use 1600x900 here but maybe your screen is really 720x640
so to bump up the kbps on the video should increase the quality of the image A LOT
avconv -f x11grab -r 30 -s 720x640 -i :0.0 -y -threads 0 -b:v 5000k ./Desktop/mydesktop.mkv
or go even higher say 7000k or even 9000k if your machine can hack it; mine struggles with 9000 ::]]
ffmpeg -f x11grab -r 30 -s 720x640 -i :0.0 -y -threads 0 -b:v 5000k ./Desktop/mydesktop.mkv
even 2500 gives you good quality ,,,, i forgot the default but it is ridiculously low hence what you saw
anyway play with the kbps see what you get ...