If you can imagine a place that requires alternate dimensions in order to access (e.g. klein bottle), you would be traveling through a different 'universe' (though it is possible that a passage through other universes could lead back to our own). If, however, the other place has a different x,y,z,t continuum, even if there is a passage between the two (wormhole), it's still a different universe.
EDIT: (Appending this) Also, if you think of the word universe, it means one totality (uni=one, verse=totality). So, if you want to refer to all that can exist, you probably want to say 'omniverse'.
It is similar in certain string theories, that patches of spacetime with different physical laws appear, this is then called the landscape. Or the multiverse in some cosmological models, where a far away region may appear, which is vastly different from or 'local' universe, that is in this case everything we can possibly observe.
So I think that it is quite possible that a theory of quantum gravity will have some object which we will call a universe, but until we have such a theory the appearance of anything outside of the universe marks highly speculative physics.
[1] That is the spacetime describing a black hole.
Tangentially, I think it may actually be appropriate to use "universe" to refer to a cosmological phenomenon (as modern physicists do), and "existence" to refer to the metaphysical phenomenon you are describing. I guess I'd have to research the etymology of "universe" before I could take a more definitive stand.