Apache error "HTTP 400 - Bad Request - Your browser sent a request that this server could not understand."

Hi,
we have two servers, which should have been set up identically (one is
a clone of the other).

When I post data from HTML forms on the first server, there is no
problems, and I can use any letters.
On the second server (on a physical different machine, but same OS ->
RH Enterprise edition), I get HTTP errors when submitting scandinavian
characters (æ, ø and å).
So when I submit the data with the scandinavian characters on the
second server, I immediately get an error message.

In Firefox (1.0.7), I get the message:
Bad Request
Your browser sent a request that this server could not understand.

In IE 6, I get a similar error:
The page cannot be found
....
HTTP 400 - Bad Request
Internet Explorer

I tried searching solutions on the net, but have no luck so far.
Any ideas how I should debug this error?
Could there be some encoding settings in the httpd.conf for this?

Regards, Per Magnus