Oooh. Dare I suggest .... configurable keys?
I too sometimes like using up and down keys to recall previous commands, but I also tend to try to use the up and down keys to edit my line of input.
Perhaps it'd be nifty if you had the up-down keys behave one way, and have command-up and command-down behave the other way, and let the user switch via Preferences which he prefers?
(I don't know how difficult such user-configurable keystrokes are ...)