GNOME always had a huge load of dependencies, and this is only getting worse as time goes by. Yes, this includes 2.x, but most of us wouldn't bother because it was popular - most would simply keep it, some would install something else, and few would have the trouble of uninstalling it.
However, since lots of people hate GNOME 3, the odds of people needing to remove all its packages rise sharply: "I DON'T WANT THAT UGLY BLOAT IN MY SYSTEM!" isn't something unheard... keeping GNOME 3.x as default DE would be counter-productive both to Debian's loyal fanbase (giving them more work) and to new users (since most potential users are turned off by retarded defaults in any distro).
Yes, there is net-inst. No, you don't need to install even the default desktop. But people, when getting in touch with a distro, will first and foremost go by the easier way - using the defaults. So, while they probably weren't lying that Debian+GNOME isn't fitting a CD anymore, it's probably the least concern that made them drop it as default.