Cannot install
During the uninstall, does it delete the entire directory? I was getting that error after an update that got interrupted. Sometimes it leaves behind a temp directory with a name that starts with a tilde (~) and that borks any further attempts. If that directory is still there, you need to delete it and try again.
Paragon City Search And Rescue
The Mentor Project
This is very similar behavior to what I get when I try to install the game on my school network unless I remember to set the IP address to an unfiltered address first. Most people using a similar network generally don't have that option but I can get an unfiltered IP when needed since I work in the Technology department and some of our software installations need to be on an unfiltered IP.
As long as I set it to an unfiltered and unblocked IP address, the game continually fails the installation with that message you gave.
Are you on a school network or another network that is using either a proxy server or internet content filter? If so, you likely won't be able to install from that network since they are blocking the communications to the server that you need.
If the game spit out 20 dollar bills people would complain that they weren't sequentially numbered. If they were sequentially numbered people would complain that they weren't random enough.
Black Pebble is my new hero.
I really don't know how to describe the problem, but here's what I've been doing:
First I uninstalled not only City of Heroes, but the NCSoft installer. Then, I installed the game through Steam. Once that was done, it made me install the latest NCSoft installer. Using that, I could update City of Heroes, but every time I try to do so, it says "Encountered an error during last operation". No matter how many times I repair, it gives me the same thing. Uninstalling and reinstalling doesn't help either, and I've done it 3 times.