dpkg diz que o pacote não está instalado e está correto, já que você não o instalou com a ferramenta de embalagem como deveria.
Ao usar um gerenciador de pacotes (como dpkg ou apt-get ), evite a instalação manual a todo custo, a menos que você deseje ter conflitos pelo resto de sua vida.
Agora você deve corrigir seu erro e instalá-lo corretamente com apt-get install gcc ou com as ferramentas relacionadas apt-get install build-essential .