Same here with kde-4.9.1. Gentoo downstream bug:
https://bugs.gentoo.org/show_bug.cgi?id=434156

I also tried to simply create new folder via the webinterface - they don't show up in kmail, even when I sunbscribe to it.

Setting status to confirmed.

I can confirm this for KDE 4.9.3 on Chakra.

Seems to be a case of "one bug covering others", because sometimes the folder isn't even created on the IMAP server. But that will be easier to triage as soon as this one here has been fixed.

Same here with Mint 13 & 14 Kde 4.9.5.

*** Bug 314466 has been marked as a duplicate of this bug. ***

I can confirm this with the latest KDE and kdepim compiled from git. I've created a folder "Mesa-dev" for a new mailing list subscription. No amount of synchronizing could make it appear, and there was an error from MySQL about a duplicate entry "Mesa-dev" in the collections table.
So I ran akonadiconsole and looked at the collections table. All other folders, for example "kde-devel", had storage locations like "/kde-devel". But Mesa-devel had "iMesa-dev"! I changed it to "/Mesa-dev", restarted Akonadi and KMail and I could finally see the folder.
See also: bug 306390 for more weirdness involving the letter "i".

I have reproduced this bug again while reproducing bug 306390, using a folder called "aiiiiiiiii". Here are the relevant Akonadi error messages with some context:

akonadi_maildispatcher_agent(11171) OutboxQueue::Private::addIfComplete: Item 734341 is queued to be sent manually.
akonadi_imap_resource_4(11169)/kdecore (KConfigSkeleton) KCoreConfigSkeleton::writeConfig:
akonadi_nepomuk_feeder(11174) Akonadi::NepomukFeederAgent::checkMigration:
akonadi_imap_resource_2(11168)/kdecore (KConfigSkeleton) KCoreConfigSkeleton::writeConfig:
Error during executing query "INSERT INTO CollectionTable (remoteId, remoteRevision, name, parentId, resourceId, cachePolicyInherit, isVirtual) VALUES (:0, :1, :2, :3, :4, :5, :6)" :  "Duplicate entry '342-a' for key 'CollectionTable_parentAndNameIndex' QMYSQL3: Unable to execute statement"
Error during insertion into table "CollectionTable" "Duplicate entry '342-a' for key 'CollectionTable_parentAndNameIndex' QMYSQL3: Unable to execute statement" 
akonadi_mixedmaildir_resource_1(11173) KMIndexReader::readHeader: DIRTY!
akonadi_mixedmaildir_resource_1(11173) KMIndexReader::readHeader: Index File sizeOfLong is 4 while sizeof(long) is 8 !
akonadi_nepomuk_feeder(11174) FindUnindexedItemsJob::itemsRetrieved: Akonadi Query took(ms):  12876
akonadi_nepomuk_feeder(11174) FindUnindexedItemsJob::itemsRetrieved: copy took(ms):  171
akonadi_mixedmaildir_resource_1(11173)/akonadiresource (maildir): "NO [LRCONFLICT] Resource akonadi_mixedmaildir_resource_1 tries to modify item 632988 ({31bf5901-6977-480b-aace-4c495bb9a4ae}) (in collection 110) with dirty payload, aborting STORE.
" 
akonadi_nepomuk_feeder(11174) FindUnindexedItemsJob::retrieveIndexedNepomukResources:
akonadi_imap_resource_4(11169)/kdecore (KConfigSkeleton) KCoreConfigSkeleton::writeConfig:
akonadi_imap_resource_2(11168)/kdecore (KConfigSkeleton) KCoreConfigSkeleton::writeConfig:
Error during executing query "INSERT INTO CollectionTable (remoteId, remoteRevision, name, parentId, resourceId, cachePolicyInherit, isVirtual) VALUES (:0, :1, :2, :3, :4, :5, :6)" :  "Duplicate entry '342-a' for key 'CollectionTable_parentAndNameIndex' QMYSQL3: Unable to execute statement"
Error during insertion into table "CollectionTable" "Duplicate entry '342-a' for key 'CollectionTable_parentAndNameIndex' QMYSQL3: Unable to execute statement" 
akonadi_nepomuk_feeder(11174) FindUnindexedItemsJob::retrieveIndexedNepomukResources: Nepomuk Query took(ms):  78769
akonadi_nepomuk_feeder(11174) FindUnindexedItemsJob::retrieveIndexedNepomukResources: Found  413  unindexed items.
akonadi_nepomuk_feeder(11174) FeederQueue::itemHeadersReceived: 9

Git commit d8fd7a28e7d6d8a89dd398311d423118ff529718 by Andras Mantia.
Committed on 28/03/2013 at 22:45.
Pushed by amantia into branch 'KDE/4.10'.

1) Fix creation of new toplevel folders (and all its subfolder): it used to generate a broken remote id and separtor ("i") causing weird problems.
2) Make sure toplevel imap folders are shown immediately, without a need to sync the account (workarounds an ETM bug 291143)
3) Warn the user if creating a folder failed on server-side and remove the folder locally. Otherwise if creation failed, it was impossible to create again a folder with the same name,
as it was already a folder with that name in the akonadi cache...
4) Make sure deleting folder "foo" doesn't deleted all folders starting with "foo" as it did before.
5) Just fix folder deletion. :) It could fail in certain cases.
6) Fix and adapt the tests.

Reporters of closed bugs: if you can still see the bug in 4.10.2, please reopen and state the details.

REVIEW: 109276
FIXED-IN: 4.10.2291143291143
Related: bug 312435, bug 301088, bug 292418, bug 305987, bug 291143

M  +6    -1    resources/imap/addcollectiontask.cpp
M  +1    -1    resources/imap/changecollectiontask.cpp
M  +16   -0    resources/imap/imapresource.cpp
M  +7    -0    resources/imap/imapresource.h
M  +11   -8    resources/imap/removecollectionrecursivetask.cpp
M  +1    -0    resources/imap/removecollectionrecursivetask.h
M  +10   -0    resources/imap/resourcetask.cpp
M  +2    -0    resources/imap/resourcetask.h
M  +4    -1    resources/imap/tests/dummyresourcestate.cpp
M  +7    -5    resources/imap/tests/testremovecollectiontask.cpp

http://commits.kde.org/kdepim-runtime/d8fd7a28e7d6d8a89dd398311d423118ff529718

I'm still seeing this bug on KDE 4.10.2, built from source on Gentoo, and I've rebooted after I installed it. Specifically to your patch, I'm running:

[I] kde-base/kdepim-runtime
     Available versions:  (4) 4.4.11.1-r1^t 4.10.1^t{tbz2} (~)4.10.2^t{tbz2}
       {aqua debug google kolab}
     Installed versions:  4.10.2(4)^t{tbz2}(10:51:10 2013-04-08)(-aqua -debug -google -kolab)

Procedure:
1. Right-click the IMAP server in the folder tree.
2. Select "Add Folder...".
3. As name, enter "Test".
4. Click "OK".

Results:
The new folder, correctly populated with Maildir subfolders, appears in the IMAP server's file system.
The new folder does not appear in KMail's folder tree.
Right-clicking the server in IMAP server in the folder tree and selecting "Update folder and its subfolders" makes no difference.
Exiting KMail, restarting Akonadi with "akonadictl stop", "akonadictl status" until everything is in state "stopped", "akonadictl start", and restarting KMail makes no difference.
Using another IMAP client to move an unread mail into the new folder makes no difference.
The only place in KMail I can see the new folder is if I right-click the IMAP server in the folder tree and select "Serverside Subscriptions...". I have server-side subscriptions turned off, and toggling it makes no difference.
Attempting to create the folder again gives this error message: "Could not create folder: Could not create collection Test resourceId: 6". This error persist even after I remove the folder on the server.

Using "kdebugdialog" to enable everything matching "kdepim" and "kmail" gives only the following output on creating a folder ("Test2" instead of "Test", since I can't create a new "Test" even after removing it on the server):

akonadi_imap_resource_0(17320)/kdepimlibs (kimap) AddCollectionTask::doStart: New folder:  "Test2"
kmail2(17355) KMKernel::instanceStatusChanged: A Resource started to synchronize, starting a mail check.
Error during executing query "INSERT INTO CollectionTable (remoteId, remoteRevision, name, parentId, resourceId, cachePolicyInherit, isVirtual) VALUES (:0, :1, :2, :3, :4, :5, :6)" :  "columns parentId, name are not unique Unable to fetch row"
akonadi_imap_resource_0(17320)/kdepimlibs (kimap) RetrieveCollectionMetadataTask::doStart: ".Test2"
kmail2(17355) KMKernel::slotProgressItemCompletedOrCanceled: Last resource finished syncing, mail check done
kmail2(17355) KMKernel::instanceStatusChanged: A Resource started to synchronize, starting a mail check.
kmail2(17355) KMKernel::slotProgressItemCompletedOrCanceled: Last resource finished syncing, mail check done
kmail2(17355) AkonadiSender::doSendQueued: Sending queued message with custom transport: ""

That "Error during executing query" message is probably not related, since it appears periodically in the terminal where Akonadi and KMail were started, regardless of actions taken in KMail.

Same here: The two top-level IMAP folders I created both cannot be seen, and akonadiserver.error contains
Error during executing query "INSERT INTO CollectionTable (remoteId, remoteRevision, name, parentId, resourceId, cachePolicyInherit, isVirtual) VALUES (:0, :1, :2, :3, :4, :5, :6)" :  "Duplicate entry '13-Stefan' for key 'CollectionTable_parentAndNameIndex' QMYSQL3: Unable to execute statement" 
Error during executing query "INSERT INTO CollectionTable (remoteId, remoteRevision, name, parentId, resourceId, cachePolicyInherit, isVirtual) VALUES (:0, :1, :2, :3, :4, :5, :6)" :  "Duplicate entry '320-KDE eV' for key 'CollectionTable_parentAndNameIndex' QMYSQL3: Unable to execute statement"

"Stefan" and "KDE eV" are the names of the folders which are not shown.

This may be related to bug #266666.

Hello. This this still happen with KDEPIM 4.14 and latest Akonadi 1.13 or even KDEPIM/Akonadi 15.08 if you can get it already. Thanks and greetings from KDE Randa Meetings, Martin

This is fixed in kdepim/kf5 at least - although I can't create top-level folders in my GMail account at all anymore (I seem to remember a commit to that effect, it was a deliberate change)... I can create subfolders of toplevel folders in KMail and that works fine.
Toplevel folders ("labels") created in the web interface do show up.