Did you solve this problem?
I am seeing this behaviour using an IBM JDK
It's clear enough that you don't have the MD5 implementation in your jboss AS..
so.. what version of the Application Server are you using?
I recomend you to use SHA-1 to encrypt your passwords.. it's more secure than MD5