Why doesn't this script work?

http://wiki.roblox.com/index.php?title=Teleport_(Method)

We see in that documentation that the second parameter to Teleport is a Player object.

I'm not sure why, but you appear to be giving it a StringValue. Just give it the player:

choosenew = 4

function selectNew()
    p = game.Players:GetChildren()
    if #p > 0 then
        -- This condition is in case there
        -- are no players.
        -- In what you have posted, it 
        -- would attempt to select anyway,
        -- and the random selection in the
        -- next line would error (and the 
        -- script would stop working from
        -- then on)
        local player = p[math.random(1,#p)];
        local msg = Instance.new("Message")
        msg.Parent = game.Workspace
        msg.Text = player.Name  ..", you're asleep now"
        wait(5)
        msg:Remove()
        game:GetService("TeleportService"):Teleport(125012407,  player);
    end
end

while true do
    selectNew()
    wait(choosenew)
end

Also, the names you've chosen for things are not very good because they are not very clear. Nothing in the name of selectNew suggests what it does: it picks a player at random and then teleports them. "teleportRandomPlayer (or sleepRandomPlayer, I'm not really sure what the context is) would be a better name.

A better API decision might be instead, however, to use teleportPlayer(randomPlayer()) (and define a new function that just picks a random player for you).

choosenew is also a poor variable name; it is a verb, yet it refers to a constant amount of time. teleportPause or teleportDelay or teleportTime would be much more appropriate names.