How does it not scale? Apt scaled to however many millions of machines run Debian and its derivatives.
If you have a really large deployment, you can set up your own repository, or a mirror of existing repositories. If that is still not enough, you're Facebook.
It's not Apt that doesn't scale, it's using apt-get manually on a large number of machines that's the problem.
By the time you're done putting all your apt-gets and your config files and whatnot in some shell script to automate it all away, you've reinvented a poor clone of puppet/ansible/chef.
I think what he meant by do not scale well is that sshing into 1000 of your servers to manually run apt-get just don't work.
apt-get is fine, it's just that at some point you need an automation tool to trigger it. A lot of chef recipes rely on the underlying package manager, that's fine.
My company runs 120 machines on AWS. For technically defensible but for this purpose irrelevant reasons, there are CentOS and Ubuntu machines in our stack. How do you propose I provision nginx on exactly the ones I want it on? How do you propose it do it for me so I'm not getting paged at 3AM?
Simple solutions regularly fail when you add zeroes.
If you have a really large deployment, you can set up your own repository, or a mirror of existing repositories. If that is still not enough, you're Facebook.