On most Debian systems /usr/bin/cc is a symlink to /etc/alternatives/cc, which in turn is a symlink to /usr/bin/gcc.
If the symlinks are there, then I'm stumped. Maybe try 'apt-get install --reinstall gcc'?