Is it to maintain backwards compatibility with older (un-genericized) versions of Collection? Or is there a more subtle detail that I am missing? I see this pattern repeated in remove also (remove(Object o)), but add is genericized as add(E e).
contains() takes an Object because the object it matches does not have to be the same type as the object that you pass in to contains(); it only requires that they be equal. From the specification of contains(), contains(o) returns true if there is an object e such that (o==null ? e==null : o.equals(e)) is true. Note that there is nothing requiring o and e to be the same type. This follows from the fact that the equals() method takes in an Object as parameter, not just the same type as the object.
Although it may be commonly true that many classes have equals() defined so that its objects can only be equal to objects of its own class, that is certainly not always the case. For example, the specification for List.equals() says that two List objects are equal if they are both Lists and have the same contents, even if they are different implementations of List. So coming back to the example in this question, it is possible to have a Collection<ArrayList> and for me to call contains() with a LinkedList as argument, and it might return true if there is a list with the same contents. This would not be possible if contains() were generic and restricted its argument type to E.
In fact, the fact that contains() takes any object as an argument allows an interesting use where you can to use it to test for the existence of an object in the collection that satisfies a certain property:
Collection<Integer> integers;
boolean oddNumberExists = integers.contains(new Object() {
public boolean equals(Object e) {
Integer i = (Integer)e;
if (i % 2 != 0) return true;
else return false;
}
});