From what I've seen, it seems to me that actually the most common issues are with "rm" rather than with "add".
It seems things mostly go like this: people installs packages with "add" until everything's fine. They may wonder why it's not called "install", and even propose to rename it, but they don't mind too much. Then something goes wrong with a package, at which point the standard immediate reaction is to try the "remove and reinstall" routine, which of course may fail in so many ways because "rm" does not really remove the package (it may actually upgrade it!)
And indeed, people get confused by this because they try stuff expecting things to work in certain way to which they're used (rather than reading the documentation, which is generally a hopeless thing to expect).
So it seems there basically a few main ways to address this:
1) revert to a more "standard" model abandoning any hope of innovation so that commands have standard names, they do what people expect, and nobody needs to understand any new thing
2) keep the current scheme but be clearer in the messages produced by the commands, so that at least people could grasp what's going on; provide convenience commands for the common situation of a broken package (or others)
3) somehow mix the two, i.e. have two layers of API, one with "install" and "delete" and another more fine-grained with "add" and "rm"
You probably can already tell I'm not a fan of the first option. Anyway, the way this is done e.g. by apt-get is to just remember which packages were explicitly installed, and which ones were just installed as dependencies. Then, there is an "autoremove" command which deletes all packages in the latter group which are no longer depended upon; you basically just do a periodic cleanup. Also, when you try to remove a package which is depended upon, you get a message telling you that if you want to remove it it will also uninstall those other packages and are you really sure? So one possibility could be following that model I suppose. It's not terrible after all.
I have no idea how the third option could work, but maybe someone more inventive than me does.
About the second option, the main change would be this: when a user calls Pkg.rm("SomePackage"), one of these things can happen
1) the package was not required and not installed: produce an error
2) the package was required, and nothing depended on it: uninstall it and that's it
3) the package was required, but it's also required by other packages: print a message detailing that the package was not removed because other packages (print which ones) depend on it
4) the package was not required, and it's only installed because of other packages: print a message which says this, and provides details like in the previous case.
Hopefully, this would remove the confusion about "rm" (at least to anyone who bothers to read the messages). Generating the detailed messages would be easy.
More details (e.g. what Leah was proposing) could also be easily added.
Some more details could be provided by Pkg.add as well (e.g. "package XYZ was already installed because...")
The other thing would be to provide some kind of "purge" or "nuke" command, which I believe was already proposed at some point.
Oh and I'm also not a fan of removing stuff from Base just because it's "not minimalist".