The most interesting information from your log file /var/log/XFree86.0.log
is
"Couldn't load XKB keymap, falling back to pre-XKB keymap"
I had the same problem and could solve it by installing the xlibs package.
Though the description of xlibs says that you don't need that package for
Debian 3.1 (sarge), it contains configuration data used by the X Keyboard
Extension.
I think this configuration data should be included in the standard
installation for X, because every user with a non-english keyboard layout
needs it.
