I think it was you whom i found Mint from and so far it seems to be pretty good although i can't say i'm too keen on their approach to a "start button" type thing...
It might have been me, but I doubt it. It is a pretty nice distro and some of their alternate desktop versions are pretty well-made. The mintmenu is completely optional and you can replace it with either of the two normal Gnome menus but yeah, I don't use it (then again, I don't use Gnome these days or have a "normal" layout myself).
Which ones would recommend though?
Depends on what you're lookin' for. There are more than 100,000 distros out there (some active, many not) and a lot of them aim for the same goals. If you want a user-friendly system with sane defaults then you've got plenty of choice and it all boils down to a combination of hardware support, what you consider "sane defaults", the availability of software, how up-to-date the software is and what desktop environment they focus on. If you're looking for something user-friendly but really light-weight, check of the LXDE edition of Mint and if you want a fairly decent KDE4 experience OpenSuse does it better than Kubuntu.
Want to dive into the deep end? Screw free time and user-friendliness, hop on the over-customised insane ride that is Gentoo. Want something like Gentoo that's fast but not as big of a pain in the rear to wrestle with? Try Arch. Want a minimal system of tiny size that's good with old hardware? Maybe some of the older versions of Puppy Linux (or some of the many spin-offs) is for you.
If you want a server, I'd have to agree with Tweak as from what I've heard, CentOS is a good choice. Want a no-nonsense, fast-boot to the internet system with firefox and a few other apps that aims to give Google's Chrome OS a run for it's money? Look up xPud. It's in development and it's hardware support seems like it could do with work but dang if it ain't fast, boots in a few seconds on my laptop. Speaking of which, if you're into this whole "fast boot internet, cloud computing" stuff, some people have got some builds of Chromium OS (The open-source foundation of Chrome OS) that you could test, especially if you've got a netbook lyin' around.
For a mix of bleeding edge packages, some degree of user-friendliness, the familiar GNOME desktop and the backing of a fairly big company, Fedora Core may be what the doctor ordered. On the opposite end of the spectrum, if stability, freedom and a community of volunteers warms your heart, give Debian a shot: it's the foundation Ubuntu was made on, is less user-friendly and tends to be more outdated but it's a lot lighter on resources.
For the adventurous, why not build your own customised distro? There are plenty of tools available for creating spin-offs of existing distros but if you really want to get your hands dirty, run a search for "Linux from scratch".
I could go on and probably actually do some searching rather than recall from memory but I'm sure you get the idea. The possibilities are almost endless, there's something to suit almost everything from supercomputers and mainframe to desktops, workstations and portable devices; whether you're a power user, programmer, sysadmin or just a regular user there's plenty of choice.
Which reminds me, there's a survey type thing somewhere on the web that asks you a series of questions and based on the answers gives you a list of suggested distros based on how well they meet your criteria. It might be a tiny bit outdated by now and doesn't have anywhere near a comprehensive list of distros but it might help. If I run into it again soon I'll throw you a link.