Padding is invalid and cannot be removed?

Rijndael/AES is a block cypher. It encrypts data in 128 bit (16 character) blocks. Cryptographic padding is used to make sure that the last block of the message is always the correct size.

Your decryption method is expecting whatever its default padding is, and is not finding it. As @NetSquirrel says, you need to explicitly set the padding for both encryption and decryption. Unless you have a reason to do otherwise, use PKCS#7 padding.