Java Security Illegal key size or default parameters

We had asked a question about this earlier, but it didn't get answered right and led nowhere.

So we've clarified a few details on the problem and we would really like to hear your ideas on how could we fix this or what should we try?

I have Java 1.6.0.12 installed on my Linux server and the code below runs just perfectly.

String key = "av45k1pfb024xa3bl359vsb4esortvks74sksr5oy4s5serondry84jsrryuhsr5ys49y5seri5shrdliheuirdygliurguiy5ru";
try {
    Cipher c = Cipher.getInstance("ARCFOUR");
    SecretKeySpec secretKeySpec = new SecretKeySpec(key.getBytes("UTF-8"), "ARCFOUR");
    c.init(Cipher.DECRYPT_MODE, secretKeySpec);
    return new String(c.doFinal(Hex.decodeHex(data.toCharArray())), "UTF-8");
} catch (InvalidKeyException e) {
    throw new CryptoException(e);
}

Today I installed Java 1.6.0.26 on my server user and when I try to run my application, I get the following exception. My guess would be that it has something to do with the Java installation configuration because it works in the first one, but doesn't work in the later version.

Caused by: java.security.InvalidKeyException: Illegal key size or default parameters
    at javax.crypto.Cipher.a(DashoA13*..) ~[na:1.6]
    at javax.crypto.Cipher.a(DashoA13*..) ~[na:1.6]
    at javax.crypto.Cipher.a(DashoA13*..) ~[na:1.6]
    at javax.crypto.Cipher.init(DashoA13*..) ~[na:1.6]
    at javax.crypto.Cipher.init(DashoA13*..) ~[na:1.6]
    at my.package.Something.decode(RC4Decoder.java:25) ~[my.package.jar:na]
    ... 5 common frames omitted

Line 25 is: c.init(Cipher.DECRYPT_MODE, secretKeySpec);