I believe the tube still runs everything through their own encoder, which I think happens to be Sorenson Spark, unless they finally upgraded to Sorenson Squeeze. Either way, it may just be them botching the transcode.
If the video file has no borders on your computer, you may try feeding YT a different file format, just to see if it handles it any better.
I might suggest feeding them an h.264 file with square pixels. Run your file through
HandBrake, changing the resolution to 640x480 and turning off "Keep Aspect Ratio."
It's worth a shot.
... yea ...