Where are you placing the listener? Is it in the application, or in the sprite that is supposed to move? Does the sprite have the focus when you are pressing the key?
Also, in adding the event listener, are you using capture? That is, are you setting the 3rd argument to true, as in
addEventListener(KeyboardEvent.KEY_DOWN, yourHandler, true)
If you use capture, which is how you have to do it if the App itself is listening for the event, then you will get a certain amount of latency, and this latency will be greater the more complex the interface is. If those events have to work their way up a vast hierarchy, this could be noticeable. If there are many sprites, this can exacerbate the problem.
What you can do is have the sprite that has the focus dispatch a custom event which a controller class listens to for each sprite. The controller class will have a handler that moves the event.currentTarget however you plan to have it done.
Also read up about custom events and how to use the SystemManager to add and remove listeners dynamically: http://livedocs.adobe.com/flex/3/langref/index.html.