Yes! Congrats!
So much for my theory :D

Does this fix not sending all notepads for you?

Changes have been made in Git (master):

commit 38064e54cade29efe021382b5a84ec168acf5d08
Author: Michael J Rubinsky <mrubinsk@horde.org>
Date:   Tue Oct 21 09:54:41 2014 -0400

     Fix determining multiplex setting for Notes.

     We were erroneously using the activesync_no_multiplex setting from
     kronolith. Possible fix for remaining issue in Bug: 13637

  .../Core/lib/Horde/Core/ActiveSync/Connector.php   |    2 +-
  1 files changed, 1 insertions(+), 1 deletions(-)

http://github.com/horde/horde/commit/38064e54cade29efe021382b5a84ec168acf5d08

OK, I think I know what's happening.

I'm hitting some sort of device, Horde or protocol limit.

I've added a new account with a couple of tasks and notes list and 
everything was merged into generic Tasks and Notes folders.

I've created a new task folder in an account which already has 
multiple folders and it was properly added to both to the device and 
Horde

The weird thing is that account stuck in the middle which has multiple 
tasks folders, but only one aggregated Notes folder.

OK. There might still be a problem if the device is offline (plane 
mode) when renaming the folder, but since the server is supposed to 
win, there shouldn't be an issue.
OK. I'll try the patch
But what can be done about that? Deleting everything in Horde doesn't 
seem to sort out the issue. Every time I add the account on the 
device, I get one Notes folder with everything in it. Horde is not 
settings things properly since I have 2 notepads and I have ticked the 
box to have separate notepads.

I do have separate tasks lists with that account though.

It syncs too quickly to generate a conflict, so the end result is the 
last name used is the one on both server and client. If there was a 
conflict it is won by the server.
This caused an issue. We weren't catching the proper exceptions. Fixed in Git.
This worked fine for me. But again, my Notes are properly being sent 
as individual folders. I.e., no '@Notes@'.

Changes have been made in Git (master):

commit 3bb531a8b0f2844475f561577e6c4700250c41ac
Author: Michael J Rubinsky <mrubinsk@horde.org>
Date:   Mon Oct 20 21:10:42 2014 -0400

     Catch more exceptions, but still throw as Horde_ActiveSync_Exception.

     Related to Bug: 13637

  .../Core/lib/Horde/Core/ActiveSync/Driver.php      |    8 ++++----
  1 files changed, 4 insertions(+), 4 deletions(-)

http://github.com/horde/horde/commit/3bb531a8b0f2844475f561577e6c4700250c41ac

What happens if you rename the notepad both on the device and in Horde?
What about if you delete the folder in Horde and try to rename it on 
the device?
Or change the default folder in Horde so that you can rename the 
previous default one. I think that's what I did with this account and 
since it wasn't working, I ended up deleting that folder.
I have no idea why this account does not work since the 3 other 
accounts sync just fine.
I've unticked the box, in order to have a single collection, but 
nothing changed, so I've re-enabled it and will update this ticket if 
I see some change.

Just verified that renaming a Notepad on the client also correctly 
propagates the change back to the server.

Ok. That's fine, and is as it should be.

I just tested this from scratch on a BB10 simulator, and I correctly 
see all of my available Notepads. I.e., NOT the @Notes@ entry. If you 
have selected to enable multiple notepad support in Mnemo's prefs, and 
it's still showing this I really have no idea what the issue is. It 
works fine here.

There is no such entry for that device in any of the email accounts 
which were added to it.

I only see that entry for Android and iOS devices

If you look in Admin->ActiveSync Devices, what is the value for the 
field "Forced Multiplex Bitmask" for that device?

OK, then there might be a bug in mnemo then because I've ticked the box
"Support separate notepads?", like in the other accounts.

Again, this line indicates that you are not using multiple folders 
from the Horde side. Horde is only sending a single multiplexed notes 
collection.

The device cannot rename the list if there is only one list.
At some point there must have been 2 lists and I probably renamed one, 
but it didn't take and I removed the lists in Horde to start from 
scratch, but the device probably never got the update and keeps 
wanting to rename the older it knows about.

I've found the log generated when re-adding the account
INFO: [30736] Horde_Core_ActiveSync_Driver::authenticate() attempt for 
user@domain.tld
INFO: [30736] PROVISION request received for user user@domain.tld
INFO: [30736] Device entry exists for BBALPHA, updating userAgent and version.
INFO: [30736] Request being handled for device: BBALPHA, Supporting 
protocol version: 14.1, Using Horde_ActiveSync v2.19.3
...
INFO: [30736] Resetting device state for device: BBALPHA, user: 
user@domain.tld, and collection: foldersync.
...
INFO: [30736] Creating new folder uuid for @Notes@: N87b0ef2f
...
DEBUG: [30736] O    <FolderHierarchy:Add>
DEBUG: [30736] O     <FolderHierarchy:ServerEntryId>
DEBUG: [30736] O      N87b0ef2f
DEBUG: [30736] O     </FolderHierarchy:ServerEntryId>
DEBUG: [30736] O     <FolderHierarchy:ParentId>
DEBUG: [30736] O      0
DEBUG: [30736] O     </FolderHierarchy:ParentId>
DEBUG: [30736] O     <FolderHierarchy:DisplayName>
DEBUG: [30736] O      Notes
DEBUG: [30736] O     </FolderHierarchy:DisplayName>
DEBUG: [30736] O     <FolderHierarchy:Type>
DEBUG: [30736] O      10
DEBUG: [30736] O     </FolderHierarchy:Type>
DEBUG: [30736] O    </FolderHierarchy:Add>
INFO: [30736] Collection without id found: a:1:{s:8:"serverid";s:7:"@Notes@";}
...
DEBUG: [30736] I    <Folder>
DEBUG: [30736] I     <SyncKey>
DEBUG: [30736] I       0
DEBUG: [30736] I     </SyncKey>
DEBUG: [30736] I     <FolderId>
DEBUG: [30736] I       N87b0ef2f
DEBUG: [30736] I     </FolderId>
DEBUG: [30736] I    </Folder>
INFO: [30736] Obtaining collection class of Notes for collection id N87b0ef2f
INFO: [30736] Collection added to collection handler: collection: 
@Notes@, synckey: NONE.
...
INFO: [30736] Initializing state for collection: @Notes@, synckey: 0
NOTICE: [30736] Horde_ActiveSync_State_Base::loadState: clearing folder state.
INFO: [30736] Resetting device state for device: BBALPHA, user: 
user@domain.tld, and collection: N87b0ef2f.
INFO: [30736] Removing collection N87b0ef2f from SyncCache.
INFO: [30736] Replacing SYNC_CACHE entry for user user@domain.tld and 
device BBALPHA: 
a:11:{s:18:"confirmed_synckeys";a:0:{}s:17:"lasthbsyncstarted";b:0;s:17:"lastsyncendnormal";b:0;s:9:"timestamp";s:10:"1413813926";s:4:"wait";b:0;s:10:"hbinterval";b:0;s:7:"folders";a:16:{s:9:"Tb6783e72";a:2:{s:5:"class";s:5:"Tasks";s:8:"serverid";s:29:"Tasks:aWnd_aKknom5TDRjkuUfzw1";}s:9:"T46c5d8e6";a:2:{s:5:"class";s:5:"Tasks";s:8:"serverid";s:29:"Tasks:qF6sS9O1HFxPNsiqP5zGBqA";}s:2:"RI";a:2:{s:5:"class";s:5:"Email";s:8:"serverid";s:2:"RI";}s:9:"N87b0ef2f";a:2:{s:5:"class";s:5:"Notes";s:8:"serverid";s:7:"@Notes@";}s:9:"Ff733e6d7";a:2:{s:5:"class";s:5:"Email";s:8:"serverid";s:13:"Archives/2012";}s:9:"Fdb3b0b7d";a:2:{s:5:"class";s:5:"Email";s:8:"serverid";s:5:"INBOX";}s:9:"Fcc785335";a:2:{s:5:"class";s:5:"Email";s:8:"serverid";s:9:"Templates";}s:9:"Fc7372765";a:2:{s:5:"class";s:5:"Email";s:8:"serverid";s:5:"Trash";}s:9:"Fa1e5c8d6";a:2:{s:5:"class";s:5:"Email";s:8:"serverid";s:10:"INBOX/spam";}s:9:"F952844e8";a:2:{s:5:"class";s:5:"Email";s:8:"serverid";s:13:"Archives/2011";}s:9:"F89ff1
48f";a:2:{s:5:"class";s:5:"Email";s:8:"serverid";s:6:"Drafts";}s:9:"F36627cfe";a:2:{s:5:"class";s:5:"Email";s:8:"serverid";s:4:"Sent";}s:9:"F1abbcf7a";a:2:{s:5:"class";s:5:"Email";s:8:"serverid";s:13:"Archives/2013";}s:9:"F1561a143";a:2:{s:5:"class";s:5:"Email";s:8:"serverid";s:8:"Archives";}s:9:"C777d0d67";a:2:{s:5:"class";s:8:"Contacts";s:8:"serverid";s:10:"@Contacts@";}s:9:"A5393f624";a:2:{s:5:"class";s:8:"Calendar";s:8:"serverid";s:10:"@Calendar@";}}s:9:"hierarchy";s:39:"{544516a4-ff8c-4cb8-837f-7810904cae96}1";s:11:"collections";a:2:{s:9:"T46c5d8e6";a:9:{s:7:"synckey";s:1:"0";s:5:"class";s:5:"Tasks";s:10:"windowsize";i:100;s:10:"truncation";i:0;s:11:"mimesupport";i:0;s:14:"mimetruncation";i:8;s:8:"conflict";i:1;s:9:"bodyprefs";a:0:{}s:8:"serverid";s:29:"Tasks:qF6sS9O1HFxPNsiqP5zGBqA";}s:9:"Tb6783e72";a:9:{s:7:"synckey";s:1:"0";s:5:"class";s:5:"Tasks";s:10:"windowsize";i:100;s:10:"truncation";i:0;s:11:"mimesupport";i:0;s:14:"mimetruncation";i:8;s:8:"conflict";i:1;s:9:"bodyprefs";
a:0:{}s:8:"serverid";s:29:"Tasks:aWnd_aKknom5TDRjkuUfzw1";}}s:13:"pingheartbeat";b:0;s:14:"synckeycounter";a:0:{}}
INFO: [30736] Old SYNCKEY: 0, New SYNCKEY: 
{544516a6-53d0-4a27-94e6-7810904cae96}1
DEBUG: [30736] O    <Folder>
DEBUG: [30736] O     <SyncKey>
DEBUG: [30736] O      {544516a6-53d0-4a27-94e6-7810904cae96}1
DEBUG: [30736] O     </SyncKey>
DEBUG: [30736] O     <FolderId>
DEBUG: [30736] O      N87b0ef2f
DEBUG: [30736] O     </FolderId>
DEBUG: [30736] O     <Status>
DEBUG: [30736] O      1
DEBUG: [30736] O     </Status>
INFO: [30736] Saving state: 
a:8:{i:0;s:39:"{544516a6-53d0-4a27-94e6-7810904cae96}1";i:1;O:21:"Horde_Db_Value_Binary":1:{s:5:"value";s:112:"C:34:"Horde_ActiveSync_Folder_Collection":65:{{"s":[],"f":"@Notes@","c":"Notes","lsd":0,"sd":0,"i":false,"v":1}}";}i:2;s:10:"BBALPHA";i:3;i:0;i:4;s:9:"N87b0ef2f";i:5;s:25:"user@domain.tld";i:6;i:0;i:7;i:1413813926;}
DEBUG: [30736] O    </Folder>
...
DEBUG: [36881] I    <Folder>
DEBUG: [36881] I     <SyncKey>
DEBUG: [36881] I       {544516a6-53d0-4a27-94e6-7810904cae96}1
DEBUG: [36881] I     </SyncKey>
DEBUG: [36881] I     <FolderId>
DEBUG: [36881] I       N87b0ef2f
DEBUG: [36881] I     </FolderId>
DEBUG: [36881] I     <WindowSize>
DEBUG: [36881] I       25
DEBUG: [36881] I     </WindowSize>
DEBUG: [36881] I     <Options>
DEBUG: [36881] I      <AirSyncBase:BodyPreference>
DEBUG: [36881] I       <AirSyncBase:Type>
DEBUG: [36881] I         1
DEBUG: [36881] I       </AirSyncBase:Type>
DEBUG: [36881] I      </AirSyncBase:BodyPreference>
DEBUG: [36881] I     </Options>
DEBUG: [36881] I    </Folder>
INFO: [36881] Obtaining collection class of Notes for collection id N87b0ef2f
INFO: [36881] Collection added to collection handler: collection: 
@Notes@, synckey: {544516a6-53d0-4a27-94e6-7810904cae96}1.

That request is the CLIENT telling the server to rename the Notes 
folder. The @Notes@ identifier signifies that is is NOT using multiple 
folders, but rather a single multiplexed source.

You said earlier your device doesn't allow renaming the notes folder, 
so I have no idea why the client is sending this request.

Of course, I keep forgetting...
  INFO: [54370] FOLDERUPDATE request received for user user@domain.tld
INFO: [54370] Device entry exists for BBALPHA, updating userAgent and version.
INFO: [54370] Request being handled for device: BBALPHA, Supporting 
protocol version: 14.1, Using Horde_ActiveSync v2.19.3
INFO: [54370] GET VARIABLES: Array
INFO: [BBALPHA] Handling FOLDER[CREATE|DELETE|CHANGE] command.
DEBUG: [54370] I  <FolderHierarchy:FolderUpdate>
DEBUG: [54370] I   <FolderHierarchy:SyncKey>
DEBUG: [54370] I     {544516a4-ff8c-4cb8-837f-7810904cae96}3
DEBUG: [54370] I   </FolderHierarchy:SyncKey>
DEBUG: [54370] I   <FolderHierarchy:ServerEntryId>
DEBUG: [54370] I     N87b0ef2f
DEBUG: [54370] I   </FolderHierarchy:ServerEntryId>
DEBUG: [54370] I   <FolderHierarchy:ParentId>
DEBUG: [54370] I     0
DEBUG: [54370] I   </FolderHierarchy:ParentId>
DEBUG: [54370] I   <FolderHierarchy:DisplayName>
DEBUG: [54370] I     Notes
DEBUG: [54370] I   </FolderHierarchy:DisplayName>
DEBUG: [54370] I  </FolderHierarchy:FolderUpdate>
INFO: [54370] Loading state for synckey 
{544516a4-ff8c-4cb8-837f-7810904cae96}3
INFO: [54370] Loading FOLDERSYNC state containing 16 folders.
INFO: [54370] 
Horde_ActiveSync_Connector_Importer::importFolderChange(N87b0ef2f, 
Notes, 0, )
INFO: [54370] Horde_Core_ActiveSync_Driver::changeFolder(@Notes@, 
Notes, 0, N87b0ef2f, )
ERR: Share name Notes not found

The device references the folder using an internal identifier, not the 
human readable form. I would need to see the synclog to see what is 
going on.

The device supports multiple collections. It's working fine with other 
accounts and this one is configured the same way.

The device doesn't allow renaming the default Notes list, but I do 
remember having added a folder and then renaming them both in Horde.
Not sure if that was already broken at this point.
Later, I also created a new list on Horde and then deleted the original list.

It seems to be a catch 22 situation because the device will always try 
to look for a folder named Notes and Horde will never be able to 
create one and always push new folders which the device won't even try 
to add because of the error 500.

Either your config, or your device do not support multiple folders per 
source. Horde combines all sources into a single virtual source before 
sending it to the client. Of course, this source cannot be renamed 
since it doesn't respond to any physical source. I don't have any 
client that allows the source to be renamed so I was unable to test 
what happened in this case.

Is that what you did to trigger this error? Tried to rename the Notes 
folder on the client?

Notes syncing usually works well, but there is one account which has 
problems. I've trying removing the relationship and re-creating the 
account, but it always fails to sync notes.

There are 2 notes lists in Horde:
Notes yyy
Notes zzz

The device sees only one list:
Notes

It puts all notes in that one folder and that folder can't be renamed.
In the logs, I see Horde returns an error 500 when the device is 
trying to sync.
I'm wondering if that's because the 2 lists start with the same name, 
but matching is probably done on something else.

One of the folders was probably named Notes to begin with and maybe 
it's cached on the device, but there should be a way for the device to 
be told to forget it. I think we've had this conversation before...

I've tried adding a new folder and nothing happens. That account is 
stuck in no-sync land.

If the relationship is broken because of caching. Is there a way to 
manually re-create it in the DB?

Here is the log:
2014-10-20T16:11:45+02:00 ERR: HORDE [mnemo] Share name Notes not 
found [pid 37467 on line 199 of 
"/usr/local/php54/lib/php/Horde/Share/Base.php"]
2014-10-20T16:11:45+02:00 ERR: HORDE Returning HTTP 500 while handling 
FolderUpdate command. [pid 37467 on line 159 of 
"/var/www/html/webmail/rpc.php"]
2014-10-20T16:11:45+02:00 ERR: HORDE Error in communicating with 
ActiveSync server: Share name Notes not found [pid 37467 on line 162 
of "/usr/local/php54/lib/php/Horde/Rpc/ActiveSync.php"]
2014-10-20T16:11:45+02:00 ERR: HORDE #0 
/usr/local/php54/lib/php/Horde/Share/Base.php(199): 
Horde_Share_Sql->_getShare('Notes')
#1 [internal function]: Horde_Share_Base->getShare('Notes')
#2 /usr/local/php54/lib/php/Horde/Core/Share/Driver.php(63): 
call_user_func_array(Array, Array)
#3 /var/www/html/webmail/mnemo/lib/Api.php(549): 
Horde_Core_Share_Driver->__call('getShare', Array)
#4 /var/www/html/webmail/mnemo/lib/Api.php(549): 
Horde_Core_Share_Driver->getShare('Notes')
#5 [internal function]: Mnemo_Api->updateNotepad('Notes', Array)
#6 /usr/local/php54/lib/php/Horde/Registry.php(1136): 
call_user_func_array(Array, Array)
#7 /usr/local/php54/lib/php/Horde/Registry.php(1093): 
Horde_Registry->callByPackage('mnemo', 'updateNotepad', Array)
#8 /usr/local/php54/lib/php/Horde/Registry/Caller.php(41): 
Horde_Registry->call('notes/updateNot...', Array)
#9 /usr/local/php54/lib/php/Horde/Core/ActiveSync/Connector.php(1257): 
Horde_Registry_Caller->__call('updateNotepad', Array)
#10 
/usr/local/php54/lib/php/Horde/Core/ActiveSync/Connector.php(1257): 
Horde_Registry_Caller->updateNotepad('Notes', Array)
#11 /usr/local/php54/lib/php/Horde/Core/ActiveSync/Driver.php(718): 
Horde_Core_ActiveSync_Connector->changeFolder('Notes', 'Notes', 'Notes')
#12 
/usr/local/php54/lib/php/Horde/ActiveSync/Connector/Importer.php(353): 
Horde_Core_ActiveSync_Driver->changeFolder('@Notes@', 'Notes', '0', 
'N87b0ef2f', false)
#13 
/usr/local/php54/lib/php/Horde/ActiveSync/Request/FolderCreate.php(151): 
Horde_ActiveSync_Connector_Importer->importFolderChange('N87b0ef2f', 
'Notes', '0', false)
#14 /usr/local/php54/lib/php/Horde/ActiveSync/Request/Base.php(253): 
Horde_ActiveSync_Request_FolderCreate->_handle()
#15 /usr/local/php54/lib/php/Horde/ActiveSync.php(880): 
Horde_ActiveSync_Request_Base->handle()
#16 /usr/local/php54/lib/php/Horde/Rpc/ActiveSync.php(143): 
Horde_ActiveSync->handleRequest('FolderUpdate', 'BBALPHA')
#17 /var/www/html/webmail/rpc.php(159): 
Horde_Rpc_ActiveSync->getResponse(NULL)
#18 {main} [pid 37467 on line 162 of 
"/usr/local/php54/lib/php/Horde/Rpc/ActiveSync.php"]