発想を変えて、Threadを使わず、Streamでparallelにしちゃうのはどうでしょうか？

import java.util.Scanner;
import java.util.stream.LongStream;

public class CountPal3 extends Thread{

    private static 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();
            long count = LongStream
                .rangeClosed(0, (max - 1) / 10000).parallel()
                .map(i -> i * 10000 + 1)
                .map(x -> LongStream.range(x, Math.min(x + 10000, max + 1))
                    .filter(CountPal3::checkPal).sum()).sum();
            System.out.println(count);
        }
    }

}

実行結果比較

$ echo 1000000000 | time java CountPal
2
50045045045040
       23.55 real        72.95 user         7.12 sys
$ echo 1000000000 | time java CountPal2
100000
50045001340240
       22.79 real        73.50 user         7.62 sys
$ echo 1000000000 | time java CountPal3
50045045045040
       19.99 real        66.79 user         0.90 sys

CountPalはswordoneさんのオリジナルコード、CountPal2はKiyoshiMotokiさんのコード、CountPal3が上のコードです。KiyoshiMotokiさんのコードが時々違う値を返すのは私にもわからないです。オリジナルのコードも値が大きいと時々違う値になるようです。脆弱性がまた出たからJava 1.8.0_92にあげたばかりなんですけど、なぜなんでしょうかね？

オリジナルやKiyoshiMotokiさんのコードが不安定になる理由(たぶん、でも自信無し)

synchronized (count) {
    count += total;
}

原因は上の部分ですが、countがLongだからではなく、countが新しいオブジェクトに置き換わっているからだと思われます。上のコードは、オートボクシングせずに、かつ、+=の糖衣構文も分解すると下記になります。

synchronized (count) {
    count = new Long(count.longValue() + total)
}

そう、countには新しいオブジェクトが代入されます。この新しいcountは、synchronized によって現在ロックされているオブジェクトではありません。でも既に置き換わっているから大丈夫？と思うかも知れませんが、そうではありません。他のスレッドがcountを評価済みの場合は排他制御が失敗します。例えば、スレッドth1、th2、th3と三つある場合を考えます。現在のcountをct1として、新しく作られる度にct2、ct3とすると次のような動作が発生すると考えらます。

スレッド(ロックオブジェクト): 処理
th1: ct1でsynchronized -> ct1のロック成功
th2: ct1でsynchronized -> th1がロック済みのため、ブロック
th1(ct1): countからct1の値を取得
th1(ct1): 取得した値(ct1)からct2を生成
th1(ct1): countにct2を代入
th1: ct1のロック解除
th2: ct1のロックが解除されたのでブロック解除、ct1のロック成功
th3: ct2でsynchronized -> ct2のロック成功 (th3が見に行くときはcountはct2になっている)
th2(ct1): countからct2の値を取得
th3(ct2): countからct2の値を取得
th2(ct1): 取得した値(ct2)からct3を生成
th3(ct2): 取得した値(ct2)からct3'を生成
th2(ct1): countにct3を代入
th3(ct2): countにct3'を代入 // th2でct3の代入は無かったことに
th2: ct1のロック解除
th3: ct2のロック解除

th2の処理は無かったことにされ、その分すくない結果となります。重要なのは、synchronized(count)でロックが取れずブロックされた時点で、countの評価が終わっており、ブロック解除された後に再評価されない(上でいうと、ct2を取得し直さずに、ct1を使おうとする)と言う点です。そのため、待たされていたスレッドは古いオブジェクトを使ってロックをかけてしまい、新しいオブジェクトでロックをしようとする他のスレッドと処理が重複します。

なお、private static Long lock = 0L;とロック用にlockを作った場合は問題は起きませんでしたので、Longオブジェクトからと言う理由ではないと思われます。synchronizedの中で代入する形であれば、Mutable/Immutableおよびラッパークラスかどうかに関係なく発生する可能性があると思われます。

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()を信用してはならない