If you install a minimal Debian server avoiding recommends, and remove a few non critical packages, you can remove python, and start building from there. No problem.
Nothing is wrong.
If you go with a default installation, and start building over there, for example a desktop system. This will remove everything else that depends on python (not only python).
And that, is probably wrong, as you do not expect to remove half of the system (and don't reinstall it back), when you try to reinstall python, like megiddo said.
Some packages that do not need python at all, depend on python because of the packaging choices, like post/pre install scripts written in python instead of shell.
Other packages that do not use python in their core functionality (for example a program written in C) depend on python because of add-on scripts or contributed extensions, shipped in the same package.
Unlike Debian, in the Ubuntu case this command is worse, because Canonical push hard for python.
Historically, many Debian packages depending on python, have been introduced or modified by maintainers/developers working for Canonical.
To install a minimal Ubuntu server without python, first you need to remove many packages (a lot), related to launchpad, or landscape, or a few other Ubuntu specific services, or stuff really intended for desktop users (not for a minimal server).
Nothing against Python or Canonical... but as I have needed to deploy servers at work with the requirement of really really minimal base, I know well about removing Python in both Linux distributions.