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