Funny, I just read mjcox entry after writting mine and found out that he's working trying to have a full CVE mapping of RedHat's advisories.
Just recently, on the debian-security mailing list Phillip Hofmeister asked if there was some way to retrieve stats easily regarding security. Well, it's not easy IMHO, but I did so (manually) for Debian some time ago (on december last year) and answered this same question in a section of the Securing Debian Manual.
However, I have recently automated the way DSAs get published on the web (here) and there are automatic ways to link DSAs to many security databases. (It's all in the web source code at the secrity template, see a DSA sample here). It should be pretty easy to automate references now (but they have to be kept uptodate).
We do need, in any case, a common database format that could be used to link many security databases like Bugtraq, CERT, CVE, ICAT. That's one of my pet projects, I will try to have an automated tool working....