Note that RH 7.x distributions (as well as RedHat Enterprise Linux 2.1) have included an old version of GCC (pre 3.x). It is known that GCC 2.96 (included in RH7.3) can compile octave (as of version 2.1.57), but the resulting binary will be bad. RedHat made available RPMs for GCC 3.1-5 through http://rhn.redhat.com (those RPMs may be available on other RPM repositories).
SuSE=Octave 2. 1. 36 is included with SuSE 8.1 . The ATLAS libraries are not included, for some reason, but the atlas. rpm for SuSE 7.3 (in the beo section) will install without problems.