I attempted to use both the solarus binary for debian and solarus compiled by me. In both cases, keyboard movement does not function properly. I have to continually tap the direction key to get the character to move in that direction. Movement is in stutters and varies distance for each tap. I checked the forum for possible cause and found none. I am runnning Ubuntu 12.04 64-bit on Linux Kernel 3.2.0-58-generic.
Strange problem. Is there a joypad connected to your computer? Sometimes it may interfere.
Have you the same problem with other games? You can try this one for example (another Zelda fangame in C++/SDL too and that also runs on Debian/Ubuntu) : http://www.zeldaroth.fr/us/zroth.php