Ubuntu 16.04 supports modern GCC-5, and you "probably" are not able to build Tahoe with this version for now. Choosing GNU-GCC4.6 as the primary compiler also (probably) won't help since Ubuntu 16.04 does not support GCC-4.6 anymore. Fortunately, there is still GCC-4.7 bindings that can be installed. Run the following:
apt install gcc-4.7
After installing GCC-4.7 you should go to Tahoe's macros directory in "~/Tahoe/macros"
open "GNU-GCC4.6.macros" with your favourite editor and change gcc, g++, gfortran to gcc-4.7, g++-4.7 and gfortran-4.7 respectively everywhere. For example take these lines in GNU-GCC4.6
COMP_C = $(GCC)/bin/gcc
COMP_CC = $(GCC)/bin/g++
COMP_F = $(GCC)/bin/gfortran
and change them to:
COMP_C = $(GCC)/bin/gcc-4.7
COMP_CC = $(GCC)/bin/g++-4.7
COMP_F = $(GCC)/bin/gfortran-4.7
try to build Tahoe and hopefully it should be fine.