В классе два поля с инвариантом (одно строго меньше другого), каждое защищено AtomicInteger. Достаточно ли этого для потокобезопасности?

Нет: AtomicInteger делает атомарными операции над отдельным полем, но не сохраняет инвариант между двумя полями. Проверка и обновление пары могут перемежаться с действиями другого потока.

Например, один поток проверит возможность увеличить нижнюю границу, а другой одновременно уменьшит верхнюю. Обе локальные проверки пройдут, но пара окажется недопустимой. Используйте общий lock для чтения и изменения пары либо AtomicReference на неизменяемое состояние с CAS всей пары. Проверка должна относиться к той же версии, которую заменяют.