My phone only? I'm pretty sure if any of the billion users deleted their maps app, they would have the exact same issue.
"The Engineering team says the only thing that can be done is to restore the device to factory settings and setting up as new and not restoring a backup."
I don't consider that to be a "fix". It's a "give up and start over". Imagine painting a canvas, then the green paint starts to peel. You ask the manufacturer how you can fix it, and they tell you that you have to wipe the entire canvas clean and paint it all over again. Would you buy the same green paint again from them?
'Insanity is doing the same thing over and over again and expecting different results. ' -Albert Einstein