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
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