I have attempted to use recordmydesktop, and the results were that the video lagged and that I got about .02 frames per minute (almost literally).
*I read that that there may be issues libtheora.
Specs Fedora 12 (64 bit)
AMD 965 black edition
250 Nvidia GTS (on 750a mobo) nf750-g55