Compiling for multiple Linux distros

Hello all,

I'm trying to compile a simple hello world program to an executable that 
will work on both my test distros; Ubuntu 7.10 & Fedora 8. Everything 
works fine when I compile and execute on the same system but I cannot 
execute a binary on Ubuntu when it was compiled in Fedora and vice-versa.

Running the Fedora binary on Ubuntu generates the error:
error while loading shared libraries: libgcj.so.8rh: cannot open shared 
object file: No such file or directory

Running the Ubuntu binary on Fedora generates:
libgcj failure: gcj linkage error.
Incorrect library ABI version detected.  Aborting.

I also tried statically linking libgcj using the -static-libgcj 
parameter but on both systems this caused the compile to fail with:
/usr/bin/ld: cannot find -lgcj

I realise that this is most likely a problem with the library versions 
in each distro but I was hoping that somebody might be able to offer 
some advice on how to generate an executable that runs on both.

Thanks for any and all advice,
Donal

================================================================
Some additional info in case it helps:
Both distros are installed on the same x86 machine.
Fedora gcj version: gcj 4.1.2 20070925
Ubuntu gcj version: gcj 4.2.1-5ubuntu5
I verified that a C program compiled with gcc was transportable between 
the two.