As you can see with some searching the Start Menu & Search issue, they not working, is quite common and occasionally occurs also in simple clean install with nothing relocated. But, as you have experienced, an almost sure way to get that error is to use Sysprep on an existing system. It works flawless for all new accounts but causes issue for existing systems.
Therefore my recommendation is either to use this method only in clean installs, or alternatively accept the facts and when doing on an existing system simply create a new administrator account, copy the data from the non-functioning old account to the new account and finally remove the old account.
You could try the free PC Mover Express to move data from old profile to new profile. Unfortunately the free version of the PC Mover requires two computers to be used and is not intended to move data from a profile to another on the same PC; if you have a spare computer to use, you would need to do it like this:
- Use PC Mover to move your personal files and settings from your PC (let's call it PC1) to PC2, a second PC you need to temporarily use. Notice that the target computer must run Windows 8 or later
- Create new administrative user on PC1
- Now move the original user data from PC2 back to PC1, to your new user profile