Since you didn't actually specify the precise commands you used, it's a little hard to know why it isn't working for you.
Unfortunately, it isn't obvious to me where Celestia gets its codecs.
However, I've found that only some of the movie file formats actually work. On my system (running WinXP), I've found that I get the best results using either "Full Frames (Uncompresseed)" or "Indeo video 5.10". Some of the other formats work, but the results don't look as good. The uncompressed frames produce a very large file, of course, but you can use your favorite video editing tool to convert them to whatever format you like.
The steps that I use are:
1) select "Capture Movie" or press Shift-F10
2) in the "Save As" popup window,
2a)browse to an appropriate directory (if necessary)
2b)specify an appropriate filename (e.g. IO) The filetype .AVI will be added automatically.
2c) select an appropriate video window size (e.g. 320x240)
2d) click on "Save"
3) in the"Video Compression" popup window,
3a) scroll up to "Indeo Video 5.10"
3b) click on "OK"
A red outline will appear, centered in your Celestia window.
Only whatever is inside that border will be recorded.
4) manipulate Celestia to get to the right starting point for your recording
5) Press F11 to start or pause the recording
6) press F12 to terminate the recording.
That's it.
Then you can
7) open a window to the directory where you saved the movie
8) double-click on the AVI file. Windows Media Player will start and display the movie.
Or otherwise manipulate the file.
Two example (trivial) movies that I created can be found on the Web page
http://www.lns.cornell.edu/~seb/celestia/blok/index.html
rgbmars.avi is the direct output from Celestia in Indeo format.
rgbmars2.wmv was converted from "Full Frame (Uncompressed)" into WMV format by Windows Movie Maker.
Does this help?