Think I've found one concurrency issue :

in 

    private void extendStateTo(final PrimeState estate, final int to) {
        if (lock.compareAndSet(false, true)) {
            // we are the thread with the lock...
            try {
                // OK, we are the only thread in here, and the state is not good
                // enough...
                // create a new state that will be good enough....
                PrimeState nextstate = extendStateInternal(estate, to);
                if (!safestate.compareAndSet(estate, nextstate)) {
                    throw new IllegalStateException(
                            "This can never happen, if it does, then shoot Monkey!");
                }
                estate.replaced();
            } finally {
                lock.compareAndSet(true, false);
            }
        } else {
            estate.waitReplaced();
        }

    }

It is possible to start waiting for an ongoing replacement, when it has already signaled it is done.

Suppose thread T1 is doing the replacement and thread T2 arrives in this method. This scheduling is possible :

 - T2 : lock compare and set returns false
 - T1 : estate.replaced executed.
 - T2 : estate.waitReplaced() : starts waiting, but the signal has been missed.

T2 is now blocked until another thread triggers a replacement and it finishes. This may even never occur.