A mensagem already installed and latest version
está se referindo à última versão do RPM (pacote binário) para a versão do Fedora. Parece que você está usando o Fedora 12, o que é bastante desatualizado. O seu melhor curso de ação provavelmente atualizará para a versão mais recente do Fedora primeiro, então você terá uma versão mais recente do GCC disponível (4.7.2).
Demora um pouco para que softwares importantes, como o GCC, passem pelo processo de criação e controle de qualidade de uma distribuição. Então, se você precisa ter o GCC 4.8.1 agora (o que parece improvável, dada a idade da sua distribuição), então você provavelmente terá que encontrar um pacote de terceiros ou compilá-lo da fonte. Independentemente disso, eu ainda recomendaria a atualização do Fedora para reduzir as complicações de dependência.