Ubuntu tells me I have packages to upgrade when I don't

It's a bug in initscripts, fixed in Natty, which copies the current state of motd to /etc/motd.tail. motd is dynamically generated whenever you boot but motd.tail is static (allowing a sysadmin to place some fixed information there for all users).

Deleting motd.tail will fix the issue temporarily but a better solution is to create an empty motd.tail. If the file doesn't exist then it may be created again (incorrectly) when initscripts is upgraded.

Create an empty motd.tail with

sudo touch /etc/motd.tail

The problem appears to be the logic in /usr/lib/update-notifier/update-motd-updates-available which is deciding that there are is no reason to run /usr/lib/update-notifier/apt-check --human-readable based on timestamps on /var/lib/update-notifier/updates-available and sources.list and a few other files.

I'm not sure what the actual bug is, but removing the cached file has at least reset it to 0 updates, although God only knows if it will show the correct number when there are updates available.

I've recently answered a similar question on Serverfault:

ubuntu server: SSH banner telling to update packages but nothing to update

That banner you're talking about is called MOTD (Message Of The Day). It appears to be a bug which can be work-arounded by deleting the /etc/motd.tail file.