There are several levels/sources of binary incompatibility.
Firstly, addressing library incompatibility
Normally, if you're running a binary on another machine, with a different version of the "same OS" (whatever that means...), then it will run fine. Completely. The issue isn't with code not working, but missing code: the bits of the OS that the binary depends on that aren't there on the target machine. It's a failure to find code to run, not to run code (which would be perfectly OK, until the point where it tried to use the missing bit!)
So, binaries from your Ubuntu gcc will most likely run on any linux system that's no older than the machine it was compiled on. It depends on exactly what functionality the binary depends on from the OS and system libraries.
Very few binaries have no external dependencies. Examine the dependencies using ldd on your output. The one most likely to cause problems is the libgcc dependency. libc and friends change very infrequently, so hardly ever cause difficulties with compatibility. GCC changes often, so will restrict the target machines your binaries will run on.
The general rule is: use as your build machine the oldest distro you want to run on. So, with a RHEL 2 build machine, you'll be able to run the binary on any system no older (with some exceptions). That's a common guideline that keeps things simple. If you need binary compatibility across lots of distros, statically linking to libstdc++ (if you use C++) is an excellent choice. Statically linking to libgcc is dangerous, and not to be attempted unless you really know what you're up to.
Finally, note that library compatibility is much simpler on other UNIX platforms; it's only linux that's such a pain. Anything compiled on AIX 6 (say) or SunOS 5.8 or HP-UX 11.00 or whatever runs with no issues on all later releases. The environment is homogenous enough that they can just ship with piles of legacy cruft in their system libraries, to guarantee that every symbol present on the old release is available on the latest one, with the same semantics.
Secondly, cross-OS binaries: run-time differences between OSes
It's all just machine code, so you might think binaries should work on other OSes. They won't. A big reason is system calls: when you need to invoke something from the kernel (which is necessary for most non-trivial functionality), you have to know how to "talk to the kernel". That is, you make a syscall and tell the OS, "do the 42 thing, you know".
The numbers for the syscalls depend on the kernel. So, the Solaris binary would be OK from linux, apart from that niggle that stops pretty much everything working.
In fact, some OSes do support the syscalls of other kernels. FreeBSD knows the linux syscalls, and when you tell it "do the 42 thing", it checks a flag in the header of your ELF, and does the appropriate action for the linux syscall numbers if the ELF is stamped as a linux one. Neat. (Of course, you need to link in linux libs as well... But, a statically linked linux binary will run fine in FreeBSD with no externals.)
Thirdly, load-time cross-OS compatibility
A binary isn't "just a binary"; it contains a whole load of meta-data that gets interpreted by the kernel before it can run the thing. Most of the binary is a blob of code and data, plus linker information. But, even something that doesn't have any external dependencies has to be parseable by the kernel.
Some kernels understand multiple binary formats, such as PE, ELF, or a.out (obsolete). The linux binaries will never run on Windows, even if they don't make any syscalls (such a binary can't exit cleanly, but for the sake of example...). That's because MS is not about to add ELF support to their kernel: the wrapper around the code that describes how it is to be loaded and started can't be read by Windows, so the code inside it won't be run: Windows doesn't know which bits of the file are even code!
