I'd start by uninstalling the application. There is no good reason why Backup Exec will stop your users connecting to the Internet, but it appears your installation is really corrupted. I have that sometimes on some of my servers, and I have to reset the login authentication to get the services started up. I suspect it's got something to do with either DNS or replication, but I haven't nailed this down yet.
Uninstall your application, and restart your server.
Put the disk in, and run through the installation. It's simply clicking "Next" until you either want to put in a different location for your installation path and SQL database, or put in licenses. Also make sure your service account you'll be using is not locked out. You cannot go wrong with a standard installation.
If it does it again, then it's got to do with authentication...that would be why your services don't start up.
