I've never heard of VectorLinux but I've used Slackware. It was good, but there isn't a real package manager. VectorLinux might have one, though.
I tried to install Fedora a few times but my system seems incompatible with it, as the live CD crashed during (and even before) installation a few times.
Currently I used Linux Mint; it's much like Ubuntu but a little more "polished", it has some useful features and is generally quite pleasant to use. However, the LiveCD takes a very long time to boot on my computer, I don't know why as other LiveCDs (such as SliTaz) take nowhere near as long. The OS itself boots ok though.
Linux Mint:
http://www.linuxmint.com/
If you don't like GNOME (I don't blame you; while it is (usually) very easy to use, it is also rather buggy and certain settings can only be accessed with gconf-editor, which is sort of like RegEdit), you can scroll down and there is also a KDE, Xfce, LXDE and a Fluxbox version (Fluxbox version is a release candidate, though; they develop them in the order I just listed so the Fluxbox version isn't final yet).
I have also used Arch Linux, which is quite easy to use and somewhat light-weight as it comes with very few programs by default. It has an excellent wiki and the package manager is far better than apt-get IMO; but it also has stability issues due to every package being taken straight from upstream sources.
The installer is text-based and a little slow, though.
Arch Linux:
http://www.archlinux.org/
The only other distribution I've used long-term (for several weeks at a time) is Ubuntu; I like it, but prefer Linux Mint. I actually stopped using Ubuntu for a similar reason to you: when I tried to upgrade to 10.04 the update manager broke a lot of things (particularly the display driver, and no amount of re-installing said driver would restore it to working order; so, I gave up and switched back to Mint).
Edit: forgot to finish a sentence.
@helios,
If you want a more up-to-date but still more-or-less stable Debian, try Debian Testing (or Debian Unstable if you want an even more up-to-date but less stable Debian).