Plesk is the control panel running on your system. There are likely many dependencies on Plesk and custom binaries installed the the Plesk software relies on. Thus, it looks like Plesk uses a repository to manage all this.
When I check out the main Plesk repository you can see there is no lucid folder: http://autoinstall.plesk.com/ubuntu/PSA_8.6.0/dists/. This probably suggests that Plesk 8.6 is not supported on lucid (10.04).
According to the Plesk website (http://www.parallels.com/products/plesk/reqs/) Plesk 10 is supported on 10.04. I would check with Plesk on the proper upgrade procedures. The repository appears to be at http://autoinstall.plesk.com/PSA_10.0.1/dist-deb-Ubuntu-10.04-i386/. But it wouldn't be wise to just change the repository URL in /etc/apt/sources.list or /etc/apt/sources.list.d without backing up the machine first.
If you are not using Plesk then it looks like their repository list erroneously includes the Plesk binaries. If this is just plain Ubuntu 8.04 then you should be able to modify the /etc/apt/sources.list to include the default Ubuntu repositories:
mv /etc/apt/sources.list /etc/apt/sources.list.backup
Then add the repositories based on https://help.ubuntu.com/community/Repositories/CommandLine. Here is an example for lucid (10.04):
deb http://us.archive.ubuntu.com/ubuntu/ lucid main restricted
deb-src http://us.archive.ubuntu.com/ubuntu/ lucid main restricted
deb http://us.archive.ubuntu.com/ubuntu/ lucid-updates main restricted
deb-src http://us.archive.ubuntu.com/ubuntu/ lucid-updates main restricted
For 8.04 you will want to replace all instances of 'lucid' with 'hardy'. Then do-release-upgrade should be able to check for new releases. I have never tried this upgrade method. But it should also update your apt sources.list to lucid for you in the process I would imagine.
Hope this helps!