Você tentou iniciá-lo no Terminal? Ele fica atrasado mesmo a partir do Terminal?
Tente iniciar o Software Center a partir do Terminal e use o comando a seguir para medir o tempo necessário para que ele seja totalmente carregado.
software-center --measure-startup-time
No meu sistema executando 12.04 demorou 6.71236896515 segundos