You don't say what Operating System you are using, but for Win98 (at least - probably similar for the others) don't worry too much if programs that you have removed are still shown in the add/remove listings. If you try to remove it again it probably won't find it. TweakUI will allow removal if you find this irritating.
Now I don't have in depth knowledge of Partition Magic, except that I know that what it does is kind of fundamental to the state of your hard drive. Is this why it won't uninstall? If not, then your error message seems to indiacte that it can't find a .dll file it needs to uninstall - a problem that I have solved in the past many times (but not with PM!) by reinstalling the application (and thus replacing any missing or damaged files) and then uninstalling it.