java.lang.IllegalAccessError: tried to access method

You are almost certainly using a different version of the class at runtime to the one you expect. In particular, the runtime class would be different to the one you've compiled against (else this would have caused a compile-time error) - has that method ever been private? Do you have old versions of the classes/jars on your system anywhere?

As the javadocs for IllegalAccessError state,

Normally, this error is caught by the compiler; this error can only occur at run time if the definition of a class has incompatibly changed.

I'd definitely look at your classpath and check whether it holds any surprises.

This happens when accessing a package scoped method of a class that is in the same package but is in a different jar and classloader.

This was my source, but the link is now broken. Following is full text from google cache:

Packages (as in package access) are scoped per ClassLoader.

You state that the parent ClassLoader loads the interface and the child ClassLoader loads the implementation. This won't work because of the ClassLoader-specific nature of package scoping. The interface isn't visible to the implementation class because, even though it's the same package name, they're in different ClassLoaders.

I only skimmed the posts in this thread, but I think you've already discovered that this will work if you declare the interface to be public. It would also work to have both interface and implementation loaded by the same ClassLoader.

Really, if you expect arbitrary folks to implement the interface (which you apparently do if the implementation is being loaded by a different ClassLoader), then you should make the interface public.

The ClassLoader-scoping of package scope (which applies to accessing package methods, variables, etc.) is similar to the general ClassLoader-scoping of class names. For example, I can define two classes, both named com.foo.Bar, with entirely different implementation code if I define them in separate ClassLoaders.

Joel