ATT should be able to tell you if the capacity is being used. I used to have their managed network services and one of the features was usage reports that showed how much capacity was being used on a particular link.
Place a network tap between the router and the LAN. See my blog series on using a network tap. Get a spare computer and install ntop and attach to the network tap port. It will give you the ability to see what all IP traffic is going across the link. It won’t show other protocols very easily though. You may need to use Wireshark to see other issues on the network.
You should check duplex settings on the LAN switch & router ports. Do not leave them set to autonegotiate. Make sure they are set to full duplex and the maximum possible speed for the devices. Remember, your LAN may be operating at 100Mbps but the WAN link is only 1.544 Mbps. VNC sessions can easily be affected by latency or packet loss. Check the LAN switch & router statistics for errors and bad packet counts.
You do have a switched network architecture, right? If not, remove any hubs and replace them with switches. Again, make sure the links are set to appropriate speed with full duplex. Wrong or mismatched duplex settings will kill a network and may not be seen until utilization is high.