This is a nightmare problem which we've fought at a number of sites. It's always ended up being the router/firewall but proving it and more importantly, fixing it is a pain in the ARS.
One site we hit this at turned out to be a firewall NAT table issue. Flushing the firewall cache fixed the problem (until it reoccurred) - maybe you could get the Cisco guys to flush the IP tables on the routers and see if that brings SCN back up. Way less intrusive than rebooting the routers.
If this does fix it temporarily, check if the routers are covered by SmartNet, and then get the IT guys to contact Cisco for config assistance (good luck with the politics).