Did you restart (turn it off and back on) the phone after you did all the deletions and uninstalls? If not, I would do that.
Should this not resolve it, then the problem may be that the update you are trying you are trying to install may well be larger than the space available.