More fun with AIX
Wild. Turns out that it was GCC. I switched from GCC 3.3.2 to IBM's xlc_r compiler, and all the problems went away. It took some doing to get the compiler flags mapped from GCC to xlc_r, but it wasn't that bad. And as a side effect, some other tools such as ldd also started working, where they hadn't before.
Lesson learned - don't use GCC for building JNI libraries for AIX.