You're probably forgetting to select Install or update bootloader. When you hit step 5 the bootloader is only temporarily in RAM, it isn't flashed to the device until you hit install. And remember to take a bootloader backup before the install as well.
Silly me, you were right! I've got it re-installed properly now, thanks!