Why is the text not changing for others?

When you want to change how a gui looks for every player, you shouldn't update the StarterGui, otherwise it won't update until they respawn. To make it change automatically, you will have to access the guis via PlayerGui which is inside each player. To do this, you will have to access each player's guis individually using a localscript. You will then need to use a server script to clone the map into the game, otherwise you'd end up crashing the game if each localscript were to do that.

player = game.Players.LocalPlayer
maintext = player.PlayerGui.Main.Header.MainText


while wait() do
 if game.Players.NumPlayers > 1 then
    maintext.Text = "Deciding what map to play"
        wait(3)
        maintext.Text = ""
        maintext.Text = "Map Chosen: " .. _G.mapChosen.Name
        wait(2)
        maintext.Text = ""
        wait(2)
    else maintext.Text = "You need 1 more player"
    end

This above script should be localscript and placed in the startergui.

map = game.ServerStorage.Maps:GetChildren()
_G.mapChosen = nil

while wait() do
    if game.Players.NumPlayers > 1 then
        wait(2)
            ranMap = math.random(1, #map)
            _G.mapChosen = map[ranMap]
        wait(3)
        mapChosenClone = _G.mapChosen:Clone()
            mapChosenClone.Parent = game.Workspace.MapHolder
    end
end

This above script should be a server script and placed in Workspace.

This may not entirely work, but this should be helpful.

------------------------ Update: Based on the fact that you posted the whole script now, I have made it so that it should work now as is. ------------------------

-- NinjoOnline --

map = game.ServerStorage.Maps:GetChildren()

while true do

--------------------------
-- Random map is chosen --
--------------------------  

    if game.Players.NumPlayers > 1 then
        for i,v in pairs(game.Players:GetPlayers()) do
        v.PlayerGui.Main.Header.MainText.Text = "Deciding what map to play"
    end
        wait(3)
     for i,v in pairs(game.Players:GetPlayers()) do
            v.PlayerGui.Main.Header.MainText.Text = ""
    end
        ranMap = math.random(1, #map)
        mapChosen = map[ranMap]
    for i,v in pairs(game.Players:GetPlayers()) do
            v.PlayerGui.Main.Header.MainText.Text = "Map Chosen: " .. mapChosen.Name
    end
        wait(2)
    for i,v in pairs(game.Players:GetPlayers()) do
            v.PlayerGui.Main.Header.MainText.Text = ""
    end
        mapChosenClone = mapChosen:Clone()
        mapChosenClone.Parent = game.Workspace.MapHolder
        wait(2)

------------------------
-- Picks random teams --
------------------------

        players = game.Players:GetChildren()

        teams = {"Bright red","Bright blue"}
        num = 1

        for i,v in pairs(players) do
            v.TeamColor = BrickColor.new(teams[num])
            num = num + 1
            if num > #teams then
                num = 1
            end
        end


---------------------------------
-- Teleport players to the map --
---------------------------------

        bspawn = mapChosenClone.BlueSpawn
        rspawn = mapChosenClone.RedSpawn

        for i,v in pairs(game.Players:GetPlayers()) do 
            name = v.Name
            check = game.Workspace:FindFirstChild(name)
            if v.TeamColor == BrickColor.new("Bright red") then
                if check then
                    checkHumanoid = check:FindFirstChild("Humanoid")
                    if checkHumanoid then
                        local distance = math.random(-4, 4);
                        check:MoveTo(rspawn.Position + Vector3.new(distance, distance, distance))
                    end
                end
            elseif v.TeamColor == BrickColor.new("Bright blue") then
                if check then
                    checkHumanoid = check:FindFirstChild("Humanoid")
                    if checkHumanoid then
                        local distance = math.random(-4, 4);
                        check:MoveTo(bspawn.Position + Vector3.new(distance, distance, distance))
                    end
                end
            end
        end


---------------------------
-- Round begins countdown --
---------------------------

        for i = 3, 1, -1 do
            game.StarterGui.Main.Header.MainText.Text = "Game begins in: " .. i
            wait(1)
            game.StarterGui.Main.Header.MainText.Text = ""
        end

-------------------------------
-- Countdown till round ends --
-------------------------------

        for i = 30, 1, -1 do
            game.StarterGui.Main.Header.MainText.Text = "Time left: " .. i
            wait(1)
            game.StarterGui.Main.Header.MainText.Text = ""
        end
        game.StarterGui.Main.Header.MainText.Text = "The round has ended"
        wait(1)
        game.StarterGui.Main.Header.MainText.Text = ""

------------------------------------        
-- Teleport players back to lobby --
------------------------------------

        for i,v in pairs(game.Players:GetPlayers()) do
            v.Character:MoveTo(Vector3.new(108, 11.19, -29))
        end
        wait(1)

---------------------
-- Destroy the map --
---------------------

        mapChosenClone:Destroy()

--------------------------------------------------
-- Needs to be 1 more player for round to begin --
--------------------------------------------------

    else
        game.StarterGui.Main.Header.MainText.Text = "You need 1 more player to join"
    end
    wait(1)
end