The exporter will only export things that are multiples of 4. My latest one is an 800x800 so that should have worked. Also, when I use modified FS2 skins and re-export them they still appear ingame. I'll put my latest skin up for download.
Actually, common practice is to make textures that are sized in powers of two, not multiples of four (or two). I'm not sure if FS2_Open even shows non-power-of-two textures, so that might be the very problem here. Even if it does it's usually better to use standardized texture sizes - if there's no other reason, at least they are then compatible with more DDS readers/editors.
<Just in case, though I think you know the difference:
Multiples of four -> 1*4, 2*4, 3*4, ... , N*4 are multiples of four.
Powers of two -> 2^1=2 2^2=4, 2^3=8, 2^4=16, 2^5=32, ... , 2^N are powers of two>
800x800 is not powers of two texture size, because it's not of form 2^X x 2^Y. 1024x1024 would be, because it's 2^10 x 2^10
By the way, what is the converter that you use? I've never heard of one that would require multiples of four texture sizes. GIMP's DDS plugin for one only converts powers of two textures. NVDxt might be able to convert non-standard textures, but there's really no reason to do that IMHO.