When I had to change from an ATI (non-Radeon) card to a nVidia TNT2 M64 long ago while I still played Morrowind, the game was one of only a few which would react badly if I had not properly disposed of the old drivers. This is another similarity to your situation.
Now for the bad news. I cannot tell you how to properly uninstall the old card's drivers - I am not even certain that it is possible at all, or that the person who replaced your graphics card did not uninstall the card's drivers. I have prepared image files of my installations in various stages of the installation process for about ten years now, and whenever there's a new piece of hardware that has to be installed, I seriously consider going back to such an image where almost no hardware-related drivers are installed. That way, I start from a system that never even had drivers for an old graphics card (or whatever was changed), and I don't have to worry about uninstalling any drivers. Uninstalling drivers has frequently led to unusable or unstable systems (at least for me), thus I try to avoid these. (Of course, I have to think about how to preserve saved games, text files and so on when putting my old operating system into the trash bin.)
I hope that someone can tell you how to verify whether it's really remnants of old drivers that prevent Morrowind from being started. If we cannot do that, then I see no other solution than to re-install Windows from scratch - hoping (but not knowing) that everything will work fine again after that. Of course, preparing images of the current state of your operating system as well as installation stages of a potential Windows re-install could really turn out beneficial.