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
This was due to my organization using our own apt repos which weren't completely up to date.