Um das Problem zu beheben gehen Sie in

C:\Users\[IhrBenutzernahme]\AppData\Roaming\
(Bei Windows XP liegen die Daten unter C:\Dokumente und Einstellungen\[IhrUsername]\Anwendungsdaten\)

Dort finden sie den Ordner Skype.
(Kann auch versteckt sein. Diesen dann über Organisieren -> Ordernoptionen -> Ansicht sichtbar machen.)

Zur Sicherheit kopieren Sie nun den Ordner Skype. Rechte Maustaste kopieren -> Rechte Maustaste einfügen und Sie haben eine Kopie von Skype

Danach gehen Sie in den Skype Ordner und löschen alles außer den Ordner mit Ihrem Skypenamen.
In diesem befindet sich Ihre History. 

Skype starten und geht wieder. :)