It means that gcc is not installed (most likely, and contrary to what you thought), or is installed in a non-standard location that's not in path, or it's not executable, or there is no symlink to gcc, just a gcc-4.3 or whatever version you use.