I got a reply from the CDN support, they think it could be a network issue between our hosting provider and the CDN's point of presence in New York, which would explain the fact that everyone impacted seems to be from out east.
I'm sending them some network info, hopefully it gets resolved soon. It looks like I've got a support guy that knows what he's doing at least, better than the first "have you tried a different browser" guy
EDIT: Just got a reply they got the info I sent and they are looking into it. I also sent them a list of ISPs that seem to be impacted.