Encrypt-then-Sign addresses this problem, but it's a design change, and it's not the case that Encrypt-then-Sign is an industrywide best practice (Practical Cryptography, for instance, recommends the opposite).
I think it depends on the encryption and signing algorithm implementation as to what works best, but then again I deal with app security and am not a cryptographer.
Encrypt-then-sign prevents the padding oracle attack; a 1 bit change to the input will immediately fail the MAC verification, preventing attackers from generating the repeated trials they need to exploit the padding error.
This doesn't depend on the algorithms you use. The padding oracle attack works just fine with DES-EDE, Serpent, AES or Twofish; HMAC-SHA1, HMAC-SHA256, and (probably) HMAC-MD5 are all equally effective at combating it.
