dass es mit dem "bloßen Löschen" der (veralteten) libertine.sty im libertine-legacy-Ordner nicht getan ist, konnte ich mir schon vorher denken: Denn sobald diese entfernt wurde, wurde die libertine.sty beim Kompilieren logischerweise vermisst.
Also fix die Datenbank geupdatet über die GUI vom tlmgr: Unter Menüpunkt "Aktionen" gibt es eine Reihe zum Auffrischen/Neu-Initialisieren/Aktualisieren der Paketliste. Jedoch führte keiner der Punkte zu einem Ergebnis, will heißen, der Prozess kam trotz ewigen Wartens nicht zum Ende und ich hatte nicht das Gefühl, dass auf der Festplatte was passiert.
(Zum Vergleich: Wenn ich die Paketliste für TeXLive aus den Repositories neu erstellen wollte, reichte ein
sudo texhash
Jedenfalls ging's hier nicht weiter, sodass die "libertine.sty" immer noch beim Kompilieren vermisst wird.
Soweit das Update.
zurückgegriffen und Kahlschlag gemacht: Alle texlive-Pakete aus den repositories deinstalliert, von Hand den Rest gelöscht. Und dann TeXLive 2012 (das ich gestern frisch von der TeXLive-Homepage geladen habe) komplett installiert. Nach ein wenig Fummelei habe ich auch meinen tlmgr dazu überreden können, nun sich selbst und alle TeXLive-Pakete zu updaten - insgesamt über 400 Stück. Im laufenden Log habe ich auch gesehen, dass libertine-legacy deinstalliert wurde.