Does the iPad youtube app work, by the way? I can't remember a time where my iPhone's youtube app has successfully streamed an entire video down without dying at some random point (over wifi - 3G seems to work but the quality is abysmal).
That said, I've never had an issue with my iPhone's youtube app either, so I don't know if there's something fundamentally different about my network and yours.