A combination of:
1) check_apt's approach to run an apt-get simulation
2) check_apt's approach to parse the apt-get simulation output to detect critical updates
3) Ubuntu placing security updates in the -updates pocket as well
Means that if apt-get chooses, in its simulation, to download a security update from -updates and not -security, then this is correct behaviour for apt (the security update will still be applied) but check_apt will not detect the update as critical from the upgrade simulation.
IMHO, check_apt is taking the wrong approach to detect critical updates here. Parsing apt-get is fragile, and is broken in this case. Instead, in an ideal world it would be able to examine the apt cache programmatically. I realise that this may not have been possible at the time that check_apt was written.
On Ubuntu, it is necessary for the desktop to prompt the user too, so there is an infrastructure for this now. If you run /usr/lib/update-notifier/apt-check, then you'll get an output like "419;0" - on my system this is telling me that I have 419 normal updates, and 0 security updates. I suggest that if /usr/lib/update-notifier/apt-check exists then you should use this instead. This will hook into the same infrastructure that the server MOTD and the Ubuntu Desktop use for security updates, so should remain reliable. On both Ubuntu Server and Ubuntu Desktop, update-notifier-common provides /usr/lib/update-notifier/apt-check and is installed by default now. I think it would be sufficient for the nagios-plugins package to Recommend the update-notifier-common package for other users. If you check that /usr/lib/update-notifier/apt-check exists before using it, and falling back to the existing behaviour if it doesn't exist, then it shouldn't anyone who doesn't have it installed.
An alternative method might be to run "apt-cache policy" for every package that you detected was downloaded in the simulation, and checking if it is available from a security repository. It looks like "apt-cache policy" will handle multiple packages at once, so this would work, but is just as fragile as the parsing of apt-get's output was in the first place.