The Ubuntu PPA has been updated with packages for Bitcoin Core 0.9.1. Ironically, they make the upgrade warning go away, but they do not fix the problem!
The Bitcoin Core packages for Ubuntu do not include a dependency on a fixed version of the OpenSSL libraries. Therefore, if you have not upgraded OpenSSL on your Ubuntu system, you will still be able to install the Bitcoin Core 0.9.1 packages. It runs just fine, and displays no warnings, yet is still vulnerable.
So upgrading to the Bitcoin Core 0.9.1 packages is neither necessary nor sufficient to remove the vulnerability. The one and only thing to do is to upgrade OpenSSL, and then (other than the warning message) it does not matter whether you use 0.9.0 or 0.9.1. Bitcoin 0.9.1 has absolutely no functional changes versus 0.9.0 (I diffed the sources).
Bitcoin 0.9.1, new OpenSSL: Not vulnerable, no warning
Bitcoin 0.9.0, new OpenSSL: Not vulnerable, displays warning
Bitcoin 0.9.1, old OpenSSL: Vulnerable, no warning
Bitcoin 0.9.0, old OpenSSL: Vulnerable, displays warning.
I will try to find the proper place to report this as a bug.
The Heartbleed bug is not in bitcoind itself, but in the OpenSSL system library on which it depends. The bug is "fixed" in Bitcoin Core 0.9.1, but all they did was to require the use of OpenSSL 1.0.1g, which incorporates the actual fix.
However, Ubuntu has not updated their distributed version of OpenSSL to 1.0.1g; instead, they have patched the version that they are using. The patched version is 1.0.1-4ubuntu5.12. Ubuntu's security advisory is posted at http://www.ubuntu.com/usn/usn-2165-1/.
Possibly as a result of this, Ubuntu packages for Bitcoin Core 0.9.1 have apparently not been created; but if you upgrade your OpenSSL libraries, it is not necessary to upgrade Bitcoin Core.
If you have the
precise-security repository in your software sources (or in
/etc/apt/sources.list), all you need to do is install the updates as you normally would, using either the update manager or
aptitude update; aptitude upgrade. If you have unattended upgrades enabled, this has probably happened already. You can check the installed version by running
dpkg -l libssl1.0.0.
Once this is done, you should restart bitcoind. (In fact, if possible you should probably reboot the system, to ensure that other potentially vulnerable services are also restarted.)
In general, upgrading Bitcoin Core does not require you to re-download the block chain.