Also, ich habe Mac OS X 10.5.2 (haltet mich nicht für dämlich, aber das ist Leopard, oder?)
Ja, das ist Leopard. Ich hatte nach 10.5 gefragt und nicht nach Leopard, weil sonst oft die Frage kommt: "Was ist Leopard?" Wie man auch fragt, es ist meistens die falsche Frage.

Keine Sorge, da hält Dich keiner für dämlich. Zum einen bist Du ja erst noch ganz neu dabei und zum anderen wissen selbst langjährige Macuser oft nicht, welches System oder welchen Prozessor sie haben. Man vergisst so was oft auch, weil es nicht so wichtig ist.

OK, also ist bei Dir und Deinen Tests soweit alles in Ordnung.
Ich habe bei Apple jemanden mit dem gleichen Problem gefunden:
HP K80 Printer Not Working With OS X 10.5.1 Die Probleme liegen daran, dass HP sich bei einigen Druckern nicht an den USB-Standard hält und das bei diesen Modellen es dann zu Schwierigkeiten kommen kann, aber nicht muss. D.h. der Druckertreiber erzeugt einen korrekten Output für den Drucker, der Transport über USB scheitert dann aber.
Hier wird genau von Deinen Problemen berichtet und als mögliche Lösung ein anderes Kabel (z.B. USB zu Parallel-Adapter) vorgeschlagen.
Hier gibt es für den Transport über USB einen anderen Treiber "usbtb". Vielleicht probierst Du den mal. Zum Drucken wird dann weiterhin der Gutenberg-Treiber verwendet, nur für den nicht funktionierenden Transport über USB der andere.
BTW, Es gibt von Gutenberg schon die Version 5.1.7. Allerdings steht in den Release Infos zu 5.1.4, dass Dein Officejet K80 ab 5.1.4 nicht mehr unterstützt wird.