Alright, I did all that and I didn't get more than 3% extra free space (around 3Mb). It did install pyoptify (that wasn't there before) and still didn't install all the stuff that depended on python back (zoutube and pygtkeditor) so those 3% are probably due to that.
Did I do something wrong?

EDIT: I actually realized that I installed the python apps that were uninstalled via apt-get install. Should that make a difference?