After some experimenting I found the cause of the issue.
When I was making changes to each sheet, I was "Duplicating" the sheet, making the chages and then making the duplicated sheet "Public". This meant that I had both the original and the edited sheet in the group of "Public sheets so I was deleting the original and keeping the amended.
It turns out that internally Qlik associates a bookmark with some kind of internal object ID instead of just the name of a sheet so although both the original and amended sheet had identical names, it was not recognising the new replaced sheet, hence the error.
The correct process of course (isn't hindsight wonderful) of making changes to a sheet is to make it "private" (from Public), make the changes and then make it "Public" again. When you are done you simply re-publish the application to the space that users have access to. This way all the bookmarks are retained and they work. Thought this might save someone lots of valuable time rebuilding their bookmarks as I just had to do for my client.