But it's not obvious (to say the least!) that all mathematical structures exist in the same sense that the physical universe exists.

In the New Scientist version of Tegmark's mathematical universes paper he writes "every mathematical structure ... has physical existence." But what does "physical" add? When we learn the word "physical" as children we are referring to objects we see, feel, hear, etc., and to the laws of nature that describe them. But clearly a radically different mathematical structure, i.e. different from our laws of nature, is not on the same page, so to speak.

Consider ghosts. Suppose that ghosts exist pretty much as Hollywood depicts them, and also suppose that ghost behaviors and abilities follow (highly complex) mathematical laws, albeit radically different laws from QM and relativity. (Have I just supposed two contradictory things? I'm pretty sure I haven't.) Would ghosts then merit the label "physical"? I think they'd still be paradigms of the nonphysical, and the radical difference of the correct descriptions of ghosts versus particles would be the dead giveaway.

If we remove the (apparently unmerited) label "physical" and just assert that mathematical structures exist, there won't be much disagreement.