I ended up having to bag out on Crypt::Tea. The first thing it does is some crazy munging of the key. I don't have enough faith in my Java coding to even attempt it.

Im going to make a stab with Crypt::CBC now. The Java 'blowfish' interpretation looks pretty straightforward.