I've been seeing a lot of as-yet unexplainable "now it works--now it doesn't" issues with a project. (It works on 8.10. Mostly it doesn't on 9.04, except for a few days in June.) Just would like to rule out that any changes from updates are having an effect. Is there a way to tell which updates were applied when?
I'd take a look at /var/log/apt/term.log.. It's a bit messy but you should find what you are looking for.
Edit: This will work as long as you use only apt (or one of its front-ends) for upgrading/installing packages (that is, as long as you don't use dpkg directly)
I don't have a machine on hand with to test this, but this thread seems to indicate that there are log files at both /var/log/dpkg.log and /var/log/apt/term.log. One of those should hopefully list updates to packages.
Ideally, you should be testing continuously with something like Buildbot or Hudson, so that you know within a day if things are broken. Not everything can be tested, though, so I don't fault you too much.
apt-cache policy <packagename>
will give you information about the current version of the installed package as well as if there are any other candidates available.
However, this give you only the current state. For the past you need to look at the logs as explained in the other answers.