Unfortunately it seems to be a Kobo server related issue.
I personally had success with the following approacj.
Attached my Kobo to the PC
Using any tool capable of working on SQLite databases updated the _isdeleted column to true in the Shelf table on all the "old" shelves. I based "old" on the values found in the LastModified column of the same table.
Once these rows had been updated, I did a WiFi sync to Kobo, and then also did a sync (with the Kobo detached) of Kobo Desktop.
Your milage may vary.
Do take backups of the database if you do try this.