Long story short, at our office network, we can't really certain things. Last.fm downloads an entire song before playing it, and YouTube loads and then all of a sudden the entire video is loaded and it plays. It won't play before hand.
iTunes radio streams fine.
Is there a router setting or something else in our network hardware that would affect this? I'm currently on a Linksys Wireless-N router (the standard black spaceship looking thing) and we have some other stuff in the server room (not exactly sure what), but if there is a setting I can look for I can go in and poke around.
The firewall appliance we have is a Fortigate of sorts, I believe a something in the 60 series.
It's a FortiGate 60M.
Talking to some other folks here, we know it's the Fortigate that's causing the problem.
EDIT: Turning off AV fixed the problem (it was expired anyway).