First, what's the output of
vssadmin list providers and
vssadmin list writers on the Exchange server? Next I'd say take a look at the event log on the Exchange server and see what events you're getting from VSS as often it will give you some indication of what exactly is going wrong. That said, I'll give you some general tips which will hopefully point you in the right direction.
I can't speak for your particular backup software, but I've had the same sort of thing with Backup Exec before. Of all the things it could do, our Exchange Server blue screened mid way through a backup. Any subsequent backups that were initiated would cripple Exchange, and any attempts to restart any of the Exchange services hung indefinitely and ultimately led to a reboot to get it up and running again (sans backup, that was).
Sorry for pointing out the obvious, but if you haven't already rebooted the server again but in a more orderly fashion, go for that and see if it resolves the problem. You might want to try just bouncing all the Exchange services, but I'm not confident that would solve your problem and I'd recommend a full reboot.
I'm assuming your backup software installs an agent of some kind on your server. Re-install that agent in case it's in some sort of inconsistent state it can't get out of. Hopefully when it uninstalls it will unregister itself with the system and re-register in a known consistent state when it is installed again. In our case, this resolved the problem.
If that doesn't work, do a backup of Exchange with the built in Windows Server backup to see if that also fails. If it doesn't crash on this, try a full backup with your backup software and see if it can cope with that. If you get one good full backup, chances are good you'll get successful incrementals and full backups going forward.