i was also one of the "complainers" about kubuntu earlier but when i tried 9.04 with KDE 4.2 it is very good. it gives a clean KDE experience without too much modification/customisation like the other distros give you. So go for Kubuntu 9.04 but it only has KDE 4.2
If you want KDE 4.3 you can still install stable kubuntu 9.04 and add the unsupported repositories mentioned in the kubuntu.org homepage and you will get KDE 4.3 which is cool
Or you can run Kubuntu 9.10 alphas if you are brave hehe.
Another very good option (but lot more work/risk) is running Arch Linux but I would say stick to Kubuntu.