You can simple add player.CharacterAdded

Remember, :connect is deprecated. use :Connect

Here is fixed script:

local datastoreService = game:GetService("DataStoreService")
local datastore = datastoreService:GetDataStore("MainSaveSystem15") --corrupted 1-14, lol

--Gets all tools in the players hand or backpack
function getTools(player)
    local array = {}
    local spot = 1
    local char = player.Character or player.CharacterAdded:Wait()
    for a, obj in pairs(char:GetChildren()) do
        if obj:IsA("Tool") then
            array[spot] = obj.Name
            spot = spot + 1
        end
    end
    local bp = player:WaitForChild("Backpack")
    for i, thing in pairs(bp:GetChildren()) do
        if thing:IsA("Tool") then
            array[spot] = thing.Name
            spot = spot + 1
        end
    end
    return array, spot --spot is the number of objects in the array
end

--Loads when they join, but not when they reset
game.Players.PlayerAdded:Connect(function(plr)
	plr.CharacterAdded:Connect(function() -- Added CharacterAdded here.
	    local MainSave = datastore:GetAsync(plr.UserId)
	    if MainSave then
	        local Table = MainSave
	        local toolArray = Table[1]
	        local toolAmount = Table[2] --amount of objects in array
	        if toolArray and toolAmount then
	            for i = 1, toolAmount do
	                local name = toolArray[i]
	                local tool = game.ReplicatedStorage:WaitForChild("Staffs"):FindFirstChild(name)
	                if tool and then -- If not find the tool clone
	                    local bp = plr:WaitForChild("Backpack")
	                    tool:Clone().Parent = bp
	                end
	            end
	        end
	    end
	end)
end)

--Save on leave
game.Players.PlayerRemoving:Connect(function(plr)
        local oldArray, count = getTools(plr)
        local saveArray = {}
        local newcount = 0 -- amount of objects in the array
        if oldArray and count then
            for i = 1, count do
                if oldArray[i] ~= nil then
                    saveArray[i] = oldArray[i]
                    newcount = newcount + 1
                end
            end
        end
        local InvItems = {}
        for _, Item in pairs(plr:WaitForChild("Inventory"):GetChildren()) do
            local Data = {}     
            Data.ItemName = Item.Name
            Data.ItemValue = Item.Value
            InvItems[#InvItems + 1] = Data
        end
        local MainLeave = {saveArray, newcount}
        datastore:SetAsync(plr.UserId, MainLeave)
end)

Hope it helped :D

Wiki pages:

CharacterAdded

Solved your problems? put [SOLVED] in title or accept a answer.