com.intellij.openapi.vcs.annotate.AnnotationListener;

This class was removed.
Could you please share your use case: what were you using it for?
Maybe com.intellij.openapi.vcs.annotate.FileAnnotation#setCloser can meet your needs?

I have the same issue. I was upgrading Plastic SCM plugin (www.plasticscm.com) plugin for IntelliJ 12.1.2.

I need AnnotationListeners to implement Plastic SCM annotate feature:

public class PlasticFileAnnotation implements FileAnnotation
{
    private final PlasticAnnotationInfo mPlasticAnnotationInfo;

    private final List<AnnotationListener> mListeners = new ArrayList<AnnotationListener>();
    private final VirtualFileAdapter mFileAdapterListener;
[...]
}

How can I implement the necessary listeners if the class no longer exist?

Thanks,
Luis

Of course, you can't implement AnnotationListeners, since they don't exist anymore.
Well, the solution is not using them. :)