Claims my value isn't a table, how do I fix this?

You're given this error because you tried using curly brackets, which are reserved for tables when you should have been using square brackets. You also tried to run two while statements without using a coroutine. Without wrapping the first while statement in a coroutine, your script will yield (wait) until that first while statement is broken out of to move on to the rest of the script. I changed that to work with the Ended event.

-- You don't need quotes on numbers
local TableOfIDs = {160594536,412765335,632668884,326087110,714630890}

-- Define variables for objects you will use later.
-- This prevents having to repeat yourself (DRY).
	-- and having errors when you don't utilize WaitForChild()

local Music = script:WaitForChild('Music')
local last_song
math.randomseed((tick() % 1) * 1e7)

local function play_newsong()
	print("new song")
	local new_song
	-- Don't want to repeat the last song!
	repeat 
		new_song = TableOfIDs[math.random(#TableOfIDs)]
	wait() 
	until new_song ~= last_song
	Music.SoundId = "http://www.roblox.com/Asset?ID="..( new_song )
	Music:Play()
	last_song = new_song
end

-- Use the Ended event instead and skip to the next song
	-- when the last song ended
Music.Ended:Connect(function()
	play_newsong()
end)

play_newsong()