First, tell us the package name. Second, in my opinion you have installed the package by using dpkg or a third source which is not in your APT repository. Anyway, cough up that name. :P
Update: There is a post which says the package is avaliable in the partner repository. You can simply comment it out in /etc/apt/sources.list , removing the "#" before the line (which contains 'partner'). (You can edit it with
sudo nano -w /etc/apt/sources.list . After that , do an
sudo apt-get update and install the packages with
sudo apt-get install sun-java6-jre (not sure if thats the correct package name, look it up using Synaptics package manager or aptitude.
Here is a post from a website.
$ sudo add-apt-repository "deb http://archive.canonical.com/ lucid partner"
$ sudo apt-get update
$ sudo apt-get install sun-java6-jre
(And yeah this seems to be the solution , its just not documented yet.)