Changes have been made in Git (master):

commit bdb81d130c9bb88d2c91e245df8bb4511822430a
Author: Michael J Rubinsky <mrubinsk@horde.org>
Date:   Thu Feb 4 17:06:36 2016 -0500

     Bug: 11563  Fix adding tags when using Kolab.

     Kolab doesn't use the UID generated by Nag_Driver::add(), but
     calculates it after, so we need to overwrite the UID that we send
     to the tagger, or else it is tagged with the incorrect UID.

     This was causing the kolab object to not be completly tagged until
     the backend was synced with Horde again - essentially creating
     orphaned rampage_object entries with the incorrect UID.

  nag/lib/Driver/Kolab.php |    1 +
  1 files changed, 1 insertions(+), 0 deletions(-)

http://github.com/horde/horde/commit/bdb81d130c9bb88d2c91e245df8bb4511822430a

The tags are actually saved correctly and even displayed inside the 
task list, just not in the tag cloud above the list.

I'll take a look at this one when I get time. Could have sworn this 
was fixed with the recent fix to tag parsing.

Still happens

@Jan: Is this fixed by the recent tag code refactoring?

Only happens when creating tasks, not when editing them, and only with Kolab.

Hi,

create a new task in nag and also create a new tag like 
"sdhjfhskjfahdsfjkhdsfjk".
Once you click the "Save" button, you'll return to the task list. The 
new tag is
not shown in the tag filter selection cloud, I takes another requests 
for it to appear.

Thomas