PublishedDateTime viene de la tabla vulnerability.
Básicamente la única diferencia que hay entre las dos consultas está en la forma de acceder a package. He usado LEFT JOIN porque no me han asegurado que todos los paquetes vayan a tener una categoría asociada.
Código:
SELECT PAK.name, count(*) as total
FROM
(SELECT P.Id as PaqID, C.name, C.Id as catID
FROM packages P
LEFT JOIN `ref_package_to_category` PC ON P.Id = PC.Package_Id
INNER JOIN Categories C ON PC.Category_Id = C.Id ) as PAK
INNER JOIN
(SELECT VTP.VulnPack_Id FROM ref_vuln_to_vulnpack VTP
INNER JOIN vulnerability V ON VTP.VulnPack_Id = V.Id
WHERE PublishedDateTime > 2008-01-01) as VP
ON VP.VulnPack_Id = PaqID
GROUP BY catID