Try this: Manual uninstallation documents for Symantec Client Security products

Granted, it's a bit of work, but you should be able to write a script to do it for you run it at the next reboot. After that, simply push the new version over and you're good to go.

I think the reason it won't uninstall is because you have already removed the previous server which stored the original password. A quicker solution may be to set up your previous server again (using whatever password you used at the time), run the uninstallation from the clients, then activate your new server and reinstall the clients.

Another option which may work is to simply reassign each client to the new server. Granted this is somewhat old information (8.x), but it should still work for newer versions. Moving one or more clients to a different parent server

Good luck!

A.J.