Maybe I was never the typical "new user" because I moved to linux from OS X after I realized that the way I was using my mac, doing everything in just the terminal and web browser, was going against the grain in apple-world, but was the "right way" in Linux.
I started by using Fedora, which worked well for me, but there were occaisional annoyances, like having to install a lot of software to /opt and /usr/local instead of making custom packages because rpms are a pain to make, and some major, and difficult to compile and configure software (specifically mono), being too out of date to satisfy dependencies for something I wanted to use (KnightOS development tools written in a recent version of C#). When I wanted to edit the configuration of some software, it was much more difficult than it needed to be because it was already running a custom configuration highly tailored to Fedora. Rather than just finding support online and doing what it said, I had to invest quite a bit of time into figuring out how the software worked, and how it integrated into the fedora system, before having a high enough level of understanding to figure out the changes that needed to be made myself.
After just 6 months of using fedora I migrated to Arch. The installation process was slightly cumbersome. I had never configured wifi using anything other than a graphical wizard, and even though netctl is really easy to use, it took some getting used to. Partitioning my drive without gparted or OS X disk utility was daunting. But none of these were too big of challenges, because the beginners guide, and the rest of the Arch Wiki, were so thorough and easy to follow.
I installed GNOME and never ran into any issues. Nothing ever broke, except when I installed incompatible video drivers, but that was my fault and easily fixable by booting from the installation disk. Unlike in fedora, almost any software I could ask for was in the official repositories, configured minimally. If it wasn't, then it was on AUR. And for the software that no one but I use, creating my own package was so incredibly trivial that it was almost easier than manually compiling from source.
A couple months later I added a second arch installation to my machine with full disk encryption (keeping around the old one because I had no where to back up to at the time). And then a couple months I replaced both installations with a cleaner (gummiboot instead of isolinux, luks on lvm rather than lvm on luks), bigger (occupying my whole drive rather than just half) arch linux installation.
Just a couple days ago I reconfigured my system to run debian and arch in dual boot with a shared home partition, both with in an lvm configuration over luks. While the debian installer was powerful relative to fedora's and ubuntu's, I found that I had to drop down into its very underpowered busybox shell several times to acheive the configuration I was going for. In comparison the Arch installer is just a full live arch installation with arch-chroot and pacstrap bundled in to be able to manage packages on a foreign system.
tl;dr I think that if you encourage new users to focus on the fundamentals of using linux, the "easy to use" distros will quickly become harder to use than the more "advanced" distros.