Sixteen bytes is 128 bits, the same as the AES/Rijndael block size. If the first 16 bytes are garbage, followed by the full message then what has probably happened is the IV has been prepended to the message, and you are trying to decrypt the IV as well as the message. To solve, extract the first 16 bytes of the incoming cyphertext and use it as the IV.
Alternatively, you have sixteen bytes of garbage followed by a partial message, missing its first 16 bytes. In this case you are probably using the wrong IV. Make sure that you are using the correct IV. Check it byte by byte to make sure it is correct. In particular, make sure that any encoding used while transferring the IV is correctly handled. If even one bit in the IV is wrong you will have a problem.