Update:
You may have a CBC mode with ciphertext stealing, it is possible to implement cbc-cts with just a cbc implementation.
Original:
Make sure that all of your data packet is ciphertext. If it's prefixed with a header or something that could through off your length and your decryption algorithm, it wouldn't complain about prefixed data, it would just decrypt to junk before getting to the end and complain about padding.
It's also common, if using authenticated encryption, to postfix your ciphertext with a mac, that would also give you a non-blocksize length multiple, but if that's the case you need to read off x last bytes and authenticate your ciphertext (commonly used is HMAC) before decrypting.
Also you make sure that you are using the right AES mode that matches the source of your ciphertext. There are some modes of AES that don't need a blocksize multiple, but they generally aren't supported in the built in .net cryptography anyway.