have you updated all packages on Ubuntu after the install? I believe lsb-core has been re-added to Ubuntu after the initial release.
apt-get update; apt-get upgrade
will upgrade all packages, but maybe a quick
sudo apt-get install lsb-core
will work out for you (altjough updating is always a good idea)
Does this solve your problem?
Johan de Groot
Installing the 'lsb' package instead of 'lsb-core' worked.
sudo apt-get install lsb