I eventually "solved" this by completely restoring my iPhone as new, deleting the old backup, and creating a new one with a new password. My iPhone was f'd up anyway with the mixed/missing icon bug. This is probably not the solution you want to hear, but it fixed the problem.