The problem with removing packages is that everything that was installed together with a package isn't necessarily removed with the package. So you may have to do some cleanup afterwards.
In other words:
If the package "foo" needs the package "bar" to work, you cannot uninstall "bar" without also uninstalling "foo". But the opposite is not true: you can uninstall "foo" without uninstalling "bar", even if "bar" was just installed as a dependency of "foo". This makes sense as other packages may also depend on "bar". So to get rid of everything that came with "foo" you may have to uninstall a few other packages separately.
Also note that configuration files are not always automatically uninstalled when you uninstall the package they belong to. If "foo" creates a directory .foo in your home folder, that directory will not be removed when you uninstall "foo". "Complete Removal" is often thought to mean that the configuration files are also removed, but with Synaptic in PCLinuxOS they aren't. You have to remove the configuration files manually.