At gertvdijk mentioned above in the comment, running:
sudo apt-get update
sudo apt-get upgrade
will fix this, if you haven't run "update" recently.
So the next question for me was, "what does the 'apt-get update' command do, and why would it matter to run it before an upgrade?" After all, the system seems to know that updates are available, so what gives?
I noticed that the first few things that were downloaded by update were 'Release.gpg' files, and googling for that filename I found this:
which states about the "WARNING: The following packages cannot be authenticated!" error, "This means that the archive has begun to be signed by a new key, which your system does not know about."
Additionally, the apt-get manpage says:
update is used to resynchronize the package index files
from their sources. The indexes of available packages are fetched
from the location(s) specified in /etc/apt/sources.list. For
example, when using a Debian archive, this command retrieves
and scans the Packages.gz files, so that information about new
and updated packages is available. An update should always be
performed before an upgrade or dist-upgrade.
Note the last sentence there. I had totally forgotten about that.
So it seems this warning simply indicates that the package index files are out of date, because the update information includes security information that helps you know that the upgrades you are downloading are, in fact, upgrades, and not horrible trojan horses that will turn your system into a spamming botnet zombie.
You can read the SecureApt page for details about how the packages are securely signed, and the chain of trust.
This all makes sense then, but now the question becomes, "what is apt-get upgrade seeing when it tries to do an upgrade with an outdated package list? How does it know there are newer versions if the package list isn't current?"
... (out of steam for research for now!)