I voted for Mandrake
It worked for me of the box install went smooth, the only thing i had a problem with was what linux users have trouble with the dreaded Winmodem.
now before Mandrake i tried Redhat 5.0,Debian,Suse 9.0 and i had various problems with them but not always the one.
with suse 9.0, it was compiling programs, no matter how i tried, it simply would not compile most source code for me with the normal commands make,make install ect.
Now with debian i would get it installed and have trouble getting it to use my Video cards 3d accel functions, most of the time i could not get X up and running at all, and configuring my modem was a pain even with the drivers.
then there was Redhat 5.0 damn thing would not find anything it seemed, well okay my old video card but that was about it,
then i quit using linux for a while thinking it was not for me at that moment in time so i read up a little on it and found that unlike most operating systems, linux is constantly evolving and growing all the time and becoming much easier than before so i gave Mandrake another shot 10.0 and have been happy ever since.
so for a newbie distro i would choose Mandrake, and i would know i am a newbie still and always will be