can you reproduce the problem if you use an american billing / shipping address?
if so, add the following code to the failure page:
<pre><?php @session_start(); var_dump($_SESSION); ?></pre>
This will write the session contents which will contain the response from the gateway to help us see what is wrong.
NOTE: The session contents will contain sensitive information that should be removed before posting here.