A Adobe tem alguns artigos muito detalhados sobre como solucionar problemas de congelamento e uma infinidade de outras coisas com o Premiere, você pode encontrá-lo aqui (Vista) ou aqui (XP).
Se nada disso ajudar, verifique o processo em execução com o Process Explorer para ver o que exatamente está fazendo na inicialização. Uma defrag , cclean , e verificação de vírus não machucaria muito também.