I came across 'delays' in my early game efforts which seemed to be related to how key repeats are handled. The way to demonstrate the effect is to open a text editor and hold down a letter key. After the first letter is displayed there is a noticeable delay after which the letter then repeats quickly (in Windows at least). I would get the same responses in my game.
My way round it is rather than respond to action directly in the overridden keylistener methods, I use them to set booleans which eliminate the 'lag' as the game movement logic now relies on the boolean values rather than the raw keypress data.
I'm not sure if this is the same problem you are experiencing, but from what you are describing it sounds very familiar to my experiences.