Do I have to restart something?
Edit: sudo apt-get update has no effect.
When I search this on another machine with the SAME sources.list, it works. But, it still doesn't work on this machine.
sudo aptitude search sun-java6-jdk
Stack Exchange network consists of 181 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.Visit Stack Exchange
Server Fault is a question and answer site for system and network administrators. It only takes a minute to sign up.Sign up to join this community
Maybe you forgot to run "apt-get update"...
After editing any configuration files in /etc/apt, you generally need to do an update;
This allows apt to update itself, it's configuration and the server(s) it queries for packages.
You might want to double check that you've got the multiverse repository included. The sun packages are in that one. For example, if you've got:
deb http://www.gtlib.gatech.edu/pub/ubuntu/ jaunty main restricted
you can tack on multiverse to the end to add it.
deb http://www.gtlib.gatech.edu/pub/ubuntu/ jaunty main restricted multiverse