I've been using Ubuntu for several months now, and while I do like it, it's started having really annoying problems such as random freezing, unresponsive programs, etc. I'd like to take this time to explore new distros, and would like some suggestions. I want to learn more about Linux, so any distro that would help with that would be awesome, and I also want customization. Stability is also important, but nothing like Debian stable that is stable to the point of being outdated.
You could try OpenSuse & Mandriva, which have the best implementations of KDE4, while they still give you the choice of Gnome. Fedora is also great, but it is probably the most cutting edge major distro so it may not be what you look in terms of stability. Not that it will crash like other OSes, but it can't be stable like Debian with all those new technologies being tested on it for the first time.
Check DistroWatch.com for some additional distros.
Any in the top 20 or so should prove to be stable and help you to learn a great deal about Linux.