Java AES decryption BadPaddingException

note: Java NOOB.

Alright, I know this has been answered a few dozen times on here, but the solutions don't seem to work/apply directly to where I understand them. (Yes, I know I don't completely understand encryption/decryption, AES, etc. but that is not the point, I am trying to understand this)

I have a utility api where I want to pass a string and return an encrypted string. Then I want to pass the encrypted string, and return a decrypted string. Simple. It works fine for many strings I pass in, but on some, I'm getting the exception javax.crypto.BadPaddingException: Given final block not properly padded.

For example, the following encrypts/decrypts fine.
util/encrypt/?token=123456789012wha = 4TR0CbCcQKqeRK73zr83aw==
util/decrypt/?token=4TR0CbCcQKqeRK73zr83aw== = 123456789012wha

The following encrypts, but does not decrypt:
util/encrypt/?token=123456789012what = NYaWmwnySoGNHyNmY9Jh+f3O2rqoLI1IAcnsl5V4OCE=
util/decrypt/?token=NYaWmwnySoGNHyNmY9Jh+f3O2rqoLI1IAcnsl5V4OCE= = exception

Here is the code in my controller:

private static final String ALGO = "AES";


@RequestMapping(value = "/util/encrypt/", method = RequestMethod.GET)
@ResponseBody
public String encrypt(HttpServletResponse httpResponse,
        @RequestParam(value = "token", required=true) String token) throws Exception 
{
    Key key = generateKey();
    Cipher c = Cipher.getInstance(ALGO);
    c.init(Cipher.ENCRYPT_MODE, key);
    byte[] encVal = c.doFinal(token.getBytes());
    String encryptedValue = Base64.encodeBase64String(encVal);
    return encryptedValue.trim();
}



@RequestMapping(value = "/util/decrypt/", method = RequestMethod.GET)
@ResponseBody
public String decrypt(HttpServletResponse httpResponse,
        @RequestParam(value = "token", required=true) String token) throws Exception 
{
    token = URLDecoder.decode(token, "UTF-8");
    Key key = generateKey();
    Cipher c = Cipher.getInstance(ALGO);
    c.init(Cipher.DECRYPT_MODE, key);
    byte[] decordedValue = Base64.decodeBase64(token);
    byte[] decValue = c.doFinal(decordedValue);
    String decryptedValue = new String(decValue);
    return decryptedValue.trim();
}



private Key generateKey() throws Exception 
{
    Key key = new SecretKeySpec(getAesKey().getBytes(), ALGO);
    return key;
}

I figure it must be something with the call Cipher.getInstance() and I've tried using Cipher.getInstance("AES/CBC/PKCS5Padding") but that always fails when decrypting. I would love to really understand what is happening here and how to fix it.