What kind of infrastructure would you need to stream video to roughly 5000 people at around 400kbps? Can anything be compressed? According to my calculations you will need a multi-gigabit uplink.

You should research "Content Delivery Networks" like Akamai, Digital Island, and such. You don't want to have that many people accessing a video stream at one location, you want to replicate the stream to a geographically-dispersed network of caches to keep network bottlenecks from being a problem. So no, you don't need a multi-gigabit uplink, just multiple uplinks.

As I understand... you provide a single stream to them, and then split it up and deliver it to the end user?

Well, I contacted a bunch of these agencies. They seem like a far worse choice. Akamai offered me $720 for 100GB of video bandwidth. For the price of a gigE uplink (~$15000) I can get 2TB of vdieo bandwidth from a Content delivery network. gigE uplink seems like a far better choice.

yegorpb,
If I could ask what did you end up doing? anything?

Colocated the servers at a datacenter

If you are looking for quality solution - you would use the AKamai solution. If you choose to use the pipe solution - I would suggest Internap.