What could be the cause of RejectedExecutionException

Just to add to OrangeDog's excellent answer, the contract of an Executor is indeed such that its execute method will throw RejectedExecutionException when the executor is saturated (i.e. there is no space in the queue).

However, it would have been useful if it blocked instead, automatically waiting until there is space in the queue for the new task.

With the following custom BlockingQueue it's possible to achieve that:

public final class ThreadPoolQueue extends ArrayBlockingQueue<Runnable> {

    public ThreadPoolQueue(int capacity) {
        super(capacity);
    }

    @Override
    public boolean offer(Runnable e) {
        try {
            put(e);
        } catch (InterruptedException e1) {
            Thread.currentThread().interrupt();
            return false;
        }
        return true;
    }

}

That essentially implements the backpressure algorithm, slowing the producer whenever the executor saturates.

Use it as:

int n = Runtime.getRuntime().availableProcessors();
ThreadPoolExecutor executor = new ThreadPoolExecutor(0, n, 1, TimeUnit.MINUTES, new ThreadPoolQueue(n));
for (Runnable task : tasks) {
    executor.execute(task); // will never throw, nor will queue more than n tasks
}
executor.shutdown();
executor.awaitTermination(1, TimeUnit.HOURS);

From ThreadPoolExecutor JavaDoc (emphasis mine)

New tasks submitted in method execute(java.lang.Runnable) will be rejected when the Executor has been shut down, and also when the Executor uses finite bounds for both maximum threads and work queue capacity, and is saturated. In either case, the execute method invokes the RejectedExecutionHandler.rejectedExecution(java.lang.Runnable, java.util.concurrent.ThreadPoolExecutor) method of its RejectedExecutionHandler. Four predefined handler policies are provided:

1. In the default ThreadPoolExecutor.AbortPolicy, the handler throws a runtime RejectedExecutionException upon rejection.
2. In ThreadPoolExecutor.CallerRunsPolicy, the thread that invokes execute itself runs the task. This provides a simple feedback control mechanism that will slow down the rate that new tasks are submitted.
3. In ThreadPoolExecutor.DiscardPolicy, a task that cannot be executed is simply dropped.
4. In ThreadPoolExecutor.DiscardOldestPolicy, if the executor is not shut down, the task at the head of the work queue is dropped, and then execution is retried (which can fail again, causing this to be repeated.)

It is possible to define and use other kinds of RejectedExecutionHandler classes. Doing so requires some care especially when policies are designed to work only under particular capacity or queuing policies.

Presumably therefore, reloading the war triggers a shutdown of the Executor. Try putting the relevant libraries in the war, so that Tomcat's ClassLoader has a better chance of correctly reloading your app.