I had the same problem, with SAME SYSTEM today and SOLVED. It may serve for you.
If you are an expert, you can jump to the end for a 3 line solution or follow my way,
that was:
1)
$ locate crt1.o
/usr/lib/x86_64-linux-gnu/Mcrt1.o
/usr/lib/x86_64-linux-gnu/Scrt1.o
/usr/lib/x86_64-linux-gnu/crt1.o
/usr/lib/x86_64-linux-gnu/gcrt1.o
/usr/lib32/Mcrt1.o
/usr/lib32/Scrt1.o
/usr/lib32/crt1.o
/usr/lib32/gcrt1.o
As I'm using x86_64, just copied "/usr/lib/x86_64-linux-gnu/"
2)
$ locate crti.o
/usr/lib/x86_64-linux-gnu/crti.o
/usr/lib32/crti.o
It was the same as above, so, nothing new.
3a)
$ locate lgcc_s
NOTHING
panic...
But, I tried:
3b)
$ locate gcc_s
/lib/i386-linux-gnu/libgcc_s.so.1
/lib/x86_64-linux-gnu/libgcc_s.so.1
/usr/lib/gcc/x86_64-linux-gnu/4.4/libgcc_s.so
/usr/lib/gcc/x86_64-linux-gnu/4.6/libgcc_s.so
/usr/lib/gcc/x86_64-linux-gnu/4.6/libgcc_s_32.so
/usr/lib/gcc/x86_64-linux-gnu/4.6/32/libgcc_s.so
/usr/lib32/libgcc_s.so.1
/usr/libexec/autopackage/libgcc_s.so.1
Now, I just choose the older version, 4.4, so just copied "/usr/lib/gcc/x86_64-linux-gnu/4.4/"
The software in question was in a makefile. Openned the one and changed:
(from)
FFLAGS=-g -O2
(to)
FFLAGS=-g -O2 -B/usr/lib/x86_64-linux-gnu/ -B/usr/lib/gcc/x86_64-linux-gnu/4.4/
To be simple: I just add -B for each path I copied
If you are using the g77 direct in terminal, may be:
$ g77 (...) -B/usr/lib/x86_64-linux-gnu/ -B/usr/lib/gcc/x86_64-linux-gnu/4.4/ (...)
Expert:
1) Use the locate to find the path of crt1.o, crti.o and-lgcc_s (search for gcc_s);
2) Copy the paths for your distro/bits;
3) Add a "-B path_1" "-B path_2" (where path_i are the paths above) in your g77 compile call.
EDIT
cogitoergosum,
In my case, the software is VERY old and fort77, gfortran and f77 gave tons of problems. I first successfully compiled with ifort (Intel Fortran compiler). But I tried g77 for an opensource alternative. And it works!