This sounds peculiarly like the issue of "DLL Hell" on the Windows platform. Ultimately, you either hope that the shared libraries match, ship with the DLLs you need, or (as a newer option) throw your chips in with WinSxS -- where the cure might actually be worse than the disease.
Maybe the fact that Java grew out of the proprietary world is part of the reason why it doesn't play nicely with open-source/free operating systems.