Here are a few ideas off the top of my head:
Try playing the file using a different xtra, sometimes different ones will work better. If you have Director 11.5, there is a native flv playback xtra.
You can build a player easily in Flash using the flvPlayback component, then bring that into Director as a swf.
Once you have the video in Director, try making the member Direct To Stage (DTS). If it is already DTS, try making it not DTS.
Make sure the video is not transparent, and nothing in Director overlaps the video... in fact, when the video is playing, nothing should be moving at all, and try to keep the amount of code that is running to a minimum.
Try lowering your video's data rate further or try using a different codec.
Using VBR (Variable Bit Rate) compression often makes the video appear to play smoother.
Try compressing the flv with different software. FFMpeg, for example, is free and does a very good job, often better than the Flash Video Encoder that comes with Flash/Creative Suite.
Also, try lowering the frame rate of the video. Depending on what sort of video you are playing, you can probably get away with knocking off a few fps, and it may make a difference in the playback quality
Thank you so much for the quick response. We did try lowering the frame rate. It didn't make a difference. We will try some of the other things you have suggested above.
Try lowering the keyframevalue.
This will make bigger files, but lower CPU.