Adobe hat einige sehr ausführliche Artikel zur Problembehandlung bei Frostproblemen und eine Vielzahl anderer Dinge mit Premiere. Sie finden sie hier (Vista) oder hier (XP).
Wenn nichts davon hilft, überprüfen Sie den laufenden Prozess mit Process Explorer, um zu sehen, was genau beim Start geschieht. Ein defrag, cReinigen und Scan - Virus würde entweder nicht viel schaden.