Double encryption / decryption fails but single does not AES 256 bit

So this particular exception is pretty common, yet my problem is slightly different from what is usually asked.

I've got a AES decrytpion and encryption function defined as followed:

    public static byte[] encrypt(byte[] ivBytes, byte[] keyBytes, byte[] textBytes)
            throws java.io.UnsupportedEncodingException,
            NoSuchAlgorithmException,
            NoSuchPaddingException,
            InvalidKeyException,
            InvalidAlgorithmParameterException,
            IllegalBlockSizeException,
            BadPaddingException {

        AlgorithmParameterSpec ivSpec = new IvParameterSpec(ivBytes);
        SecretKeySpec newKey = new SecretKeySpec(keyBytes, "AES");
        Cipher cipher;
        cipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
        cipher.init(Cipher.ENCRYPT_MODE, newKey, ivSpec);
        return cipher.doFinal(textBytes);
    }

    public static byte[] decrypt(byte[] ivBytes, byte[] keyBytes, byte[] textBytes)
            throws java.io.UnsupportedEncodingException,
            NoSuchAlgorithmException,
            NoSuchPaddingException,
            InvalidKeyException,
            InvalidAlgorithmParameterException,
            IllegalBlockSizeException,
            BadPaddingException {

        AlgorithmParameterSpec ivSpec = new IvParameterSpec(ivBytes);
        SecretKeySpec newKey = new SecretKeySpec(keyBytes, "AES");
        Cipher cipher = Cipher.getInstance("AES/CBC/PKCS5Padding");
        cipher.init(Cipher.DECRYPT_MODE, newKey, ivSpec);
        return cipher.doFinal(textBytes);
    }

Now if I perform a single decryption like this:

System.out.println(Arrays.toString(
                AES256Cipher.decrypt(ivBytes, HexBytePlainWriter.hexStringToByteArray(aKeys[a]),
                        AES256Cipher.encrypt(ivBytes, HexBytePlainWriter.hexStringToByteArray(aKeys[a]),
                                AES256Cipher.encrypt(ivBytes, HexBytePlainWriter.hexStringToByteArray(bKeys[b]), HexBytePlainWriter.hexStringToByteArray(zkeys[a^b]))
                                )
                        )));

The byte array outputs just fine. Whereas if I perform double encryption/decryption:

        System.out.println("dec: " + HexBytePlainWriter.ByteToHexString(
            AES256Cipher.decrypt(ivBytes, HexBytePlainWriter.hexStringToByteArray(aKeys[a]),
                    AES256Cipher.decrypt(ivBytes, HexBytePlainWriter.hexStringToByteArray(bKeys[b]),
                            AES256Cipher.encrypt(ivBytes, HexBytePlainWriter.hexStringToByteArray(aKeys[a]),
                                    AES256Cipher.encrypt(ivBytes, HexBytePlainWriter.hexStringToByteArray(bKeys[b]), HexBytePlainWriter.hexStringToByteArray(zkeys[a^b]))
                                    )
                            ))));

I get the famous javax.crypto.BadPaddingException: Given final block not properly padded Exception. Note that a and b are just integers (assume they are both 0). Currently, the IVBytes is just an empty byte array of size 16, declared with new byte[16]. and aKeys and bKeys are both String arrays with AES encypted (random) strings (length 32 bytes).

These are the helper functions I use (to turn byte[] into a hex string and vice versa):

public static  String ByteToHexString (byte[] data) {
        StringBuilder buf = new StringBuilder();
        for (byte b : data) {
            int halfbyte = (b >>> 4) & 0x0F;
            int two_halfs = 0;
            do {
                buf.append((0 <= halfbyte) && (halfbyte <= 9) ? (char) ('0' + halfbyte) : (char) ('a' + (halfbyte - 10)));
                halfbyte = b & 0x0F;
            } while (two_halfs++ < 1);
        }
        return buf.toString();
    }

    public static byte[] hexStringToByteArray(String s) {
        int len = s.length();
        byte[] data = new byte[len / 2];
        for (int i = 0; i < len; i += 2) {
            data[i / 2] = (byte) ((Character.digit(s.charAt(i), 16) << 4)
                                 + Character.digit(s.charAt(i+1), 16));
        }
        return data;
    }

I suspect that the output of the first decryption malforms the ciphertext in such a way that the outer part throw the exception. I've check the size and the outer part outputs 32 bytes, so that should be OK. Does this not comply with the PKC5Padding?

Any help is much appreciated.

Edit:

It looks like my minimal example was faulty: I used key B first instead of A. Jon Skeet did give me an idea though. I will edit if I've got anything new.

Edit2:

The idea was correct. I was looping over a Garbled truth table (for those interested, check this Wikipedia article) and checking all possible ciphertexts (CT). The problem was if you pick an incorrect CT and use double decryption on it, it will throw the exception because the first decryption returns garbage. A simple check on the keys in the table fixed this.