I'm going to second what crouchingpenguin said, and recommend that you use Crypt::CBC. Not only will it deal with block length, it also makes your encryption more secure.

It's hard to tell what's wrong with your decryption without looking at the encryption. It seems extrememly dubious that you are doing substitutions such as $tmp =~ s/\%u20AC/\%80/gi; on the cryptext. Cryptext is pure binary. It should not be treated as character data.