IMHO, it's not really the distro, it's the way you approach it. I started with CorelLINUX; before everyone starts with the Corel/POS, I agree; it WAS a POS. Corel had a really nice little GUI installer, and if everything went OK, it was a breeze to install; you ended up at a modified KDE desktop that looked like Windows- it was just like being home!! There was an underlying problem that I , as a total newbie didn't understand; Corel wasn't secure- not one bit!! It would allow the root user to act as a day-to-day user without ever making him aware that the whole system was wide open to anything that could happen to it. That, in the long run , wasn't a majpr problem. Corel never gave any indication of Linux's strongest point: the CLI! The command line is where Linux is most powerful, and Corel ignored that advantage TOTALLY. That effectivly crippled me as a Linux user for a long time; I'm still not completely comfortable using it, but I'm getting better at it now.
The point I'm trying to make is this; WHATEVER distribution you decide suits you best, use the command line as much as possible; THERE'S where you're going to learn the most; a pretty desktop is a nice feature, no doubt about it, but the REAL power is in the CLI.