Yeah i thought i understood why but i was thinking about somthing else. I just doesn't make any sense to me. If the Collection is marked to hold a specific type then is should be legal to insert that type into the Collection. I simplified the code by taking out the super class.
Code:
 import java.util.*; 

 class Employee{
  public String dept; 
  public String empid; 
  public String fname; 
  public String lname;
  public Employee(String dept, String empid, String fname, String lname){
   this.dept = dept; 
   this.empid = empid; 
   this.fname = fname; 
   this.lname = lname; 
  }
 }

class Aux{
  public static void listEmployee(Collection<Employee> e){
   for(Employee employee: e){
    System.out.print(employee.fname);
   }
  }
 }

 public class Directory{
  public static void main(String[] args){
   Set<Employee> directory = new TreeSet<Employee>(); 
   directory.add(new Employee("Shipping","9878","Bill","Gates"));
   directory.add(new Employee("Mailroom","6546","John","Holmes"));
   Aux.listEmployee(directory);
  }
 }