The difference is between local (method) variables vs class member variables. A member variable exists during the lifetime of the enclosing object, so it can be referenced by the inner class instance. A local variable, however, exists only during the method invocation, and is handled differently by the compiler, in that an implicit copy of it is generated as the member of the inner class. Without declaring the local variable final, one could change it, leading to subtle errors due to the inner class still referring to the original value of that variable.
Update: The Java Specialists’ Newsletter #25 discusses this in more detail.
Even the compiler error is misleading to me.
Cannot refer to a non-final variable message inside an inner class defined in a different method: Different from what?
From the inner class’ run method I believe.