Seems to be a few people getting caught out with this. Take a look at Failed update missing table and the issue referenced in there.
One of the big things that affected us was that when doing a large number of updates the restore may not work properly. We spent a lot of time trying things and it was not until we started again from a full db and app server restore that we were able to progress using the steps given by support.
Note as well that when doing the rebuild database, watch the sessions in the database as the ui looks like it has finished when it has not on some of the larger updates.
It can be done though