There's several galaxies in the starcraft universe. Where does Starcraft Universe take place? Multiple galaxies? A single sector? 1 Planet? That may help with the production of a new name.
I'm pretty sure that the name Universe summons up all the galaxies. Also I think it's simply going to be anywhere the storyline took places so expect Char and Aiur.
Those are great name setups. Whenever I am creating a map that needs a name of a Hero, Team, Spells I use a similar setup too! Its fun coming up with fictional names.
The (Starcraft noun) (synonym for army) (synonym for strength) of (name of a mythology god) (name of a character)'s (name of a weapon) (two words that create an oxymoron - ie hell angels) A current map project I am working on is called War of Fantasia - The Fight of Gods, Demons and Heroes. It is a risk-type map using a fictional map terrain that has over 40 fictional nations using names of mythology.
Some examples: The Titan Shield Celestial Light The Fenix Fellowship Kerrigan's Plague Looking Glass League
Back to the post... again, the name of this project is Starcraft Universe. The map will be set in battles seen in the campaign of SC1, SC2 and read from Starcraft fictional books.