waitメソッドは1つのスレッドがもう一つのスレッドのからのnotifyメソッドの呼び出しを待機するだけのものなので、
今回のように1つのスレッドが複数のスレッドの終了を待つようなケースには不向きです。
https://docs.oracle.com/javase/jp/6/api/java/lang/Object.html#wait()

恐らく不可能ではないでしょうが、管理用のスレッドを別に用意するなど、複雑な実装になりそうです。

代わりに、CountDownLatchクラスを使用することをお勧めします。

マニュアルに

ほかのスレッドで実行中の操作セットが完了するまで、1 つ以上のスレッドを待機可能にする同期化支援機能です。

とある通り、まさに今回のようなケースに有用なクラスです。
http://docs.oracle.com/javase/jp/7/api/index.html?java/util/concurrent/CountDownLatch.html

CountDownLatchクラスを使うと、ご提示のコードは以下のように書き直すことができます（Java7で動作確認）。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.CountDownLatch;

public class CountPal extends Thread {

    private static Long count = 0L;

    // リストを同期化する必要はなくなる。
    private static List<CountPal> threads = new ArrayList<CountPal>();

    private final long from;
    private final long until;

    private CountDownLatch doneSignal = null;

    public CountPal(long from, long until) {
        this.from = from;
        this.until = until;
    }

    public void setDoneSignal(CountDownLatch doneSignal) {
        this.doneSignal = doneSignal;
    }

    @Override
    public void run() {
        if (doneSignal == null) {
            throw new IllegalStateException("doneSignal is null.");
        }

        long total = 0L;
        for (long i = from; i < until; i++) {
            if (checkPal(i)) {
                total += i;
            }
        }
        synchronized (count) {
            count += total;
        }

        doneSignal.countDown();
    }

    private boolean checkPal(long i) {
        String str = Long.toString(i);
        int m = 0;
        int n = str.length() - 1;
        while (m < n) {
            if (str.charAt(m) != str.charAt(n)) {
                return false;
            }
            m++;
            n--;
        }
        return true;
    }

    public static void main(String[] args) {
        try (Scanner s = new Scanner(System.in)) {
            long max = s.nextLong();
            for (long x = 1; x <= max; x += 10000) {
                CountPal temp = new CountPal(x, Math.min(x + 10000, max + 1));
                threads.add(temp);
            }

            System.out.println(threads.size());

            CountDownLatch doneSignal = new CountDownLatch(threads.size());
            for (CountPal thread : threads) {
                thread.setDoneSignal(doneSignal);
                thread.start();
            }

            try {
                doneSignal.await();
            } catch (InterruptedException e) {
                System.out.println(e);
            }

            // 変数countは、読み取り時も同期化する必要がある。
            synchronized (count) {
                System.out.println(count);
            }
        }
    }

}

ちなみに、変数countは、読み取り時も同期化する必要があります。
http://www.ibm.com/developerworks/jp/java/library/j-praxis/pr50.html
http://d.hatena.ne.jp/j5ik2o/20110220/1298215999

もしくは、AtmicLongクラスに置き換えても良いかもしれません。
http://docs.oracle.com/javase/jp/7/api/index.html?java/util/concurrent/CountDownLatch.html

あと、私の環境(*)だと、ご提示のコードと私のコードはともに変数maxが700000を超えた頃から計算結果が不安定になり、
ときどき異なる値を出力することがありました。

*
  OS : Mac OSX 10.9 
  CPU : Intel Core i7 (64bit)
  メモリ : 8Gb
  JDK1.7

詳しく調べてはいませんが、生成するスレッドの数が多すぎて、途中で死んでいるものがあるのかもしれません。

 訂正

ちなみに、変数countは、読み取り時も同期化する必要があります。 

は誤り。

なぜなら、CountDownLatchクラスは以下を保証しているため。

メモリー整合性効果:countDown() を呼び出す前のスレッド内のアクションは、別のスレッド内の対応する await() から正常に復帰したあとのアクションよりも happen-before です。

https://docs.oracle.com/javase/jp/6/api/

"happens-before"については、以下を参照。
https://docs.oracle.com/javase/specs/jls/se6/html/memory.html#17.4.5

全てのスレッド終了を待機したいなら、全てのスレッドにjoin()するだけで良いのでは？

「どう修正すべきか」は他の方の回答で触れられていますので、そちらに譲ります。

調べるとwait()やnotifyAll()を使うらしいことはわかったのですが、何に対してこのメソッドを使えばいいのかがわかりません。 

(あくまで私見ですが）java.lang.Objectクラスのwait(),notify(),notifyAll()メソッドは、その動作仕様を多くのJavaプログラマに正しく理解されておらず、ほとんどのケースで間違って使われる機能だと思います。

Java 1.0時代から存在する機能ですが、非常に原始的なスレッド間同期機構のため、可能な限り利用を避けることをおすすめします。Java 1.5以降はjava.util.concurrentパッケージにスレッド間同期のツール群が導入されたため、そちらを探せば大抵の欲しい機能は提供されると思います。

Webでよく見かける、下記のようなwait()コード例は完全に誤っています。

try {
  wait();
} catch (InterruptException e) {}

少なくとも「スプリアス・ウェイクアップ(Spurious Wakeup)」に言及していない解説は、全て誤っていると解釈して差し支えありません。正しい使い方は下記記事に譲ります。

• waitについてのまとめ
• 条件変数とspurious wakeup
• スプリアスウェイクアップ問題 – Javaのwait() / notify()を信用してはならない