Convert them to flash video first.
File size should be under the minimum and they will be uploaded faster because youtube doesn't have to convert them.
If you have Flash CS3 or Flash 8 it comes with a Video Encoder which you should use, if not then there are a few free alternatives.
One of my personal favorites because its simple to use is the Riva FLV 2.0 Encoder: http://www.rivavx.com/index.php?encoder&L=3
(download link on that same page about half way down).
Another alternative is SUPER
which is also free, just a little harder to use. It can convert to a number of other video formats as well.
Also in the future if you plan on putting a video on you tube, change the recording resolution to 320 x 240 because I believe thats what youtube uses. Could be 640 x 480.