Why would an Enum implement an Interface?

Enums don't just have to represent passive sets (e.g. colours). They can represent more complex objects with functionality, and so you're then likely to want to add further functionality to these - e.g. you may have interfaces such as Printable, Reportable etc. and components that support these.

The Comparable example given by several people here is wrong, since Enum already implements that. You can't even override it.

A better example is having an interface that defines, let's say, a data type. You can have an enum to implement the simple types, and have normal classes to implement complicated types:

interface DataType {
  // methods here
}

enum SimpleDataType implements DataType {
  INTEGER, STRING;

  // implement methods
}

class IdentifierDataType implements DataType {
  // implement interface and maybe add more specific methods
}

Here's one example (a similar/better one is found in Effective Java 2nd Edition):

public interface Operator {
    int apply (int a, int b);
}

public enum SimpleOperators implements Operator {
    PLUS { 
        int apply(int a, int b) { return a + b; }
    },
    MINUS { 
        int apply(int a, int b) { return a - b; }
    };
}

public enum ComplexOperators implements Operator {
    // can't think of an example right now :-/
}

Now to get a list of both the Simple + Complex Operators:

List<Operator> operators = new ArrayList<Operator>();

operators.addAll(Arrays.asList(SimpleOperators.values()));
operators.addAll(Arrays.asList(ComplexOperators.values()));

So here you use an interface to simulate extensible enums (which wouldn't be possible without using an interface).