I have the same issue, it RARELY works on the first load but after 2-15+
(!) refreshes it works (yes, I am willing to wait for it to refresh that many times to watch a video that is shorter than the time it takes to refresh).
Firefox 3 on Vista Home Prem SP1
Seemed to happen after FF3, not because of FF3, but just coincidentally YouTube fscked up the service at the same time. I have friends that complain of the same thing on occasion, but for me it is near constant.
EDIT: 3/3 video loads worked first try via IP and not
www.youtube.com, FYI