Как удалить все пробелы и знаки препинания в строке, чтобы код распознавал палиндромы?

Видимо, это вопрос Java, а не JavaScript.

Хороший способ выяснить, почему ваш код не делает того, что, по вашему мнению, он должен делать, — это отладить его. Любая современная IDE может вам в этом помочь. Или просто распечатывайте значения соответствующих переменных (здесь userInput) после каждого изменения.

После этого вы увидите, что userInput имеет значение "Never" после того, как вы набрали Never odd, or even!. Это потому, что in.next() дает вам следующий токен (следующее слово). Если вы замените это на in.nextLine(), код будет работать как положено. Значит, проблема не имела никакого отношения к звонку replaceAll.

Я внес в вашу программу несколько исправлений и одно дополнение.

import java.text.Normalizer;
import java.util.Scanner;

public class Palindrome {

   public void init() {
      System.out.println( "CSE110 Palindrome - TAOLIN DEINIOL\n" );    
      String userInput;
      while( true ) {
         Scanner in = new Scanner( System.in );
         System.out.println( "Input statement, or type'done' to quit:" );

           // change "next" to "nextLine", to read a complete entry
         userInput = in.nextLine();
         userInput = userInput.toLowerCase();
         userInput = userInput.replaceAll( "\\p{Punct}", "" );

           // remove accents and other modifiers
         userInput = Normalizer.normalize( userInput, Normalizer.Form.NFD )
                .replaceAll( "[^\\p{ASCII}]", "" );
         System.out.println( userInput );
         userInput = userInput.replaceAll( " ", "" );
         System.out.println( userInput );
         if ( userInput.equals( "done" ) ) {
            break;
         }

           // remove the intermediate step, call directly to "isPalindrome"
           // change the name of this method, to avoid collision with the name of the class
         isPalindrome( 0, userInput.length() -1, userInput );
      }
   }

   public boolean isPalindrome( int i, int j, String A ) {
      if ( i >= j ) {
         System.out.println( "That is a Palindrome.\n" );
         return true;
      }
      if ( A.charAt( i ) != A.charAt( j ) ) {
         System.out.println( "That is NOT a Palindrome.\n" );
         return false;
      }
      return isPalindrome( i + 1, j - 1, A );
   }


   public static void main( String[] args ) {
      Palindrome aa = new Palindrome();
      aa.init();
   }
}

В основном методе создайте только объект Palindrome и вызовите свой метод init, таким образом я избегаю уродливой (ненужной) статики.

Это работает путем удаления всех небукв [^a-z] (путем замены на ничего) и использования StringBuilder для переворачивания символов:

Scanner in = new Scanner(System.in);
while (true) {
    System.out.println("Input statement, or type 'done' to quit:");
    String userInput = in.nextLine();
    if (userInput.equals("done")) {
        break;
    }
    userInput = userInput.toLowerCase().replaceAll("[^a-z]", "");
    boolean isPalindrome = new StringBuilder(userInput).reverse().toString().equals(userInput);
    System.out.format("%s is%s a palindrome\n", userInput, isPalindrome ? "" : " not");
}