Ich möchte mich hier noch einmal selbst einbringen, da wir das Problem inzwischen selbst lösen konnten. Ich bin mir sicher, dass das Problem mit den nicht sichtbaren neu angelegten Kategorien bei weitem kein Einzelfall sein kann.
Das Problem war in unserem Falle, dass Presta eine Kategorie nicht ordnungsgemäß gelöscht hat. Das bedeutet, es waren noch "Reste" der gelöschten Kategorie in der Datenbank vorhanden.
In der Datenbank wird die Position bzw. die Reihenfolge mit "nleft" und "nright" Angaben und der ID der Elternkategorie "parent_id" gespeichert, woraus dann auch der Kategoriebaum erzeugt wird.
In unserem Beispiel wurde für nleft 415 und für nright 416 und 318 für parent_id erzeugt. Dies setzt sich dann jeweils bei nleft und nright immer um 1 erhöht für die nächste Kategorie fort. Bei der nicht korrekt gelöschten Kategorie waren diese beiden Werte auf 0.
Dadurch konnten für die neu angelegte Kategorie im Kategoriebaum keine korrekten Werte geschrieben werden, woraus folgte, dass Presta damit nichts anfangen kann - die Kategorie wird nicht angezeigt! Ebenso konnten deswegen die Berechtigungen(wer darf die Kategorie sehen->Kunden, Besucher, Gäste) nicht in die Datenbank geschrieben werden.