Well MD5 is a standard so presuming MySQL's implementation is correct the only way the two are not going to match is if the values you pass are different. Your guess about character encodings is probably correct - assuming you have checked carefully that it is nothing so simple as a typo? You are probably aware that String.getBytes() returns an encoding of a String in the platform's default character set. You could probably check that this is consistent with the character set used in your MySQL database.
MessageDigest.digest() returns a byte[], and new String(byte[]) converts those bytes directly to characters using the platform's default. However, you're probably expecting a hex-string like "a8ce923f27d1...", and I'd bet the library you found does that conversion for you.