Ubuntu 8.04 Install Image Updates
That said, it seems that default images here are kept pretty up-to-date, at least when it comes to Ubuntu 8.04 (don't know about other distros). For example, when I rebuilt my Linode a couple of weeks after the Debian OpenSSL bug was found, the default Ubuntu 8.04 image was already patched.
The simplest way to ensure your setup is working is to install some new package.
apt-get dist-upgrade is considered to be rather dangerous in ubuntu environment, for distribution upgrades "do-release-upgrade" should be used, while to resolve possible lockups between packages, "apt-get install packagename" does the trick.
Also, your situation is surely not related to this case, when there are packages not upgraded (which would be upgraded by dist-upgrade), apt-get upgrade shows them on the "not upgraded" list.