Binding M- / M- in Emacs 23.1.1

I'm trying to put in a feature that I miss from Eclipse, where Alt+[Up/Down] transposes the lines up or down, but can not for the life of me figure out how to assign to these keys properly. I am using it in -nw mode (so just in a shell window), and typically run in a screen session.

Using a global key binding, I can get it to work with letter combinations, like (kbd "M-m"), but every combination I have tried for the arrow keys just gives me a message that doesn't make sense, I always get:

"ESC <up> is undefined"

What I have tried:

(global-set-key (kbd "M-<up>") 'transpose-line-up)    
(global-set-key (kbd "<escape>-<up>") 'transpose-line-up)
(global-set-key [M-up] 'transpose-line-up)
(global-set-key [\e \M-O A] 'transpose-line-up)

And C-h c just returns:

ESC <up> (translated from ESC M-O A) is undefined

None of these work, either using ESC or Alt.

Any idea how I can make this work? I would prefer to have these as Alt+[Up/Down] just because that is what I am used to.

Edit

From the comments:

• C-q Up prints ^[OA.

• C-q M-Up prints ^[ and moves the cursor up a line.

• C-h k (Alt+Up) prints ESC (translated from ESC M-O A) is undefined.

Thanks for the suggestions, but they all turned out the same.