/opt/amd/gnutools-4.1.1/bin/ld: /opt/amd/gnutools-4.1.1/lib/gcc/x86_64-redhat-linux/4.1.1-amd-rhel4/libstdc++.a(stdexcept.o): relocation R_X86_64_32S against `vtable for std::logic_error' can not be used when making a shared object; recompile with -fPIC
/opt/amd/gnutools-4.1.1/lib/gcc/x86_64-redhat-linux/4.1.1-amd-rhel4/libstdc++.a: could not read symbols: Bad value

Judging from the above, I think that your GCC compiler is not configured to use shared libraries by default, so it takes a static version of libstdc++, which is not suitable to produce shared objects. As far as I know, Red Hat 4.4 has an older compiler version than 4.1.1, so I assume it was upgraded later, and might be misconfigured that time.

I looked in GCC online docs but did not find an option to forcefully use shared libraries (though the opposite option, -static, is present). So it's unclear if we could force using shared libraries with TBB and eliminate dependency on a particular compiler configuration.

As Alexei said, RH 4.4 doesn't support gcc 4.x. In addition, ld is separate from gcc. It's certainly common to require a better ld than what comes with RH 4.4, but it's generally done at your risk. You give us no clue where yours came from, or whether it's a standard configuration. A standard ld would use .so libraries by default if those are present, so the presumption is that required .so libraries aren't present on the paths set in your g++ installation (g++ -print-search-dirs)
If you file an issue with Intel support, you should at least give the result of ld --version, in addition to the standard requested information. However, with so much non-standard about your configuration, it could be difficult to pin down.