To be frank: I think that the Kubuntu’s switch to “Text aside icons” (as discussed by Seele) was a mistake. The reasons for that are best explained by an example:

Here, only one of three actions are visible in the tool bar, rendering it pretty useless. But let’s revisit what we had as the default in KDE 3 before we used “Text below icons”:

Now, “Text below icons” is a bad idea, because it wastes vertical space, which we are already short of (Plasma panels, menu bar, window decoration). Given the emerging 16:9 ratio monitors, this sounds like a call for “Text aside icons”, the new Kubuntu default:

During the quite vivid and productive discussions on Seele’s blog, some people proposed to show the text only for special actions (mockup as posted there). This does not only allow to easily spot the most important of the actions (keep in mind that all actions in the toolbar should be kind of important, otherwise they shouldn’t be there), but also eases hitting the actions tool button.
Actually, this idea has gone through my mind quite often and our friends over at the competition used this for ages, albeit for Evolution only. Instead of going for such a solution, KDE has struggled for years searching for the right defaults and discussed about screen resolutions.
The actual reason for this was mostly of technical nature: QToolBar couldn’t change the tool button style property for specific actions in Qt 3.x, and the almighty XMLGUI layer used by KDE thus had no such option either. Instead, one everyone got to pick his poison (no description, or space wasting ones).
Attentive readers will have noticed my deliberate use of the past tense in the paragraphs above. This is because with Qt 4, it is possible to do just what I said was missing: Adding actions with an individual Qt::ToolBarStyle. So without further ado, here is my (code-backed) mockup:

The secret is to add those actions that should get a text aside the icon like this:
...
QToolBar *bar = mw.addToolBar(QObject::tr("Actions"));
bar->setIconSize(QSize(22, 22));
QToolButton *tb = new QToolButton;
tb->setDefaultAction(new QAction(QIcon(":/icons/mail-message-new.png"),
QObject::tr("New Message"), tb));
tb->setToolButtonStyle(Qt::ToolButtonTextBesideIcon);
bar->addWidget(tb);
...
This is officially documented behavior. Quoting the Qt docs on QToolBar::addWidget():
If you add a QToolButton with this method, the tools bar’s Qt::ToolButtonStyle will not be respected.
Now it shouldn’t be too hard to add suppport this idiom to XMLGUI, by adding a flag for “important” actions. That said, XMLGUI is a quite complicated and fragile matter. However, I will take a look at this soon to see if it can be implemented in a clean way without patching Qt.
PS: I think this is one example where less could actually be more in KDE. If we get this right, there is no need for choosing an icon label alignment at all.