Please run the following code:

import java.text.*;
import java.util.*;
import java.io.*;

class FormatTester
{
    // Constants. Modify to your needs.
    static String timeZoneID = "ECT";
    static int THREADNUMBER = 3;
    static int ITERATIONS = 1000;

    // The format of the date preceeding all log file entries.
    static SimpleDateFormat simpleDateFormat;

    static PrintWriter log;

    public static void main(String[] args)
    {
        TestThread[] testThreadArray = new TestThread[FormatTester.THREADNUMBER];

        System.out.println("This is FormatTester.");

        // Initialize date format and set up the correct time zone.
        simpleDateFormat = new SimpleDateFormat("yyyyMMdd-HHmmss");
        simpleDateFormat.setTimeZone(TimeZone.getTimeZone(FormatTester.timeZoneID));

        Date date = new Date();
        String timeStamp = FormatTester.simpleDateFormat.format(date);
        String logFileName = timeStamp + "-log.txt";
        File logFile = new File(System.getProperty("user.dir"), logFileName);
        FileOutputStream logFileOutputStream = null;

        try
        {
            logFileOutputStream = new FileOutputStream(logFile);
        }
        catch (IOException e)
        {
            System.out.println("Cannot create log file. " + e);
            System.out.println("Exiting.");
            System.exit(1);
        }

        log = new PrintWriter(logFileOutputStream, true);

        for (int i = 0; i < FormatTester.THREADNUMBER; i++)
        {
            testThreadArray[i] = new TestThread();
            testThreadArray[i].start();
        }

        System.out.println("Up and running.");
    }
}

class TestThread extends Thread
{
    public void run()
    {
        for (int i = 0; i < FormatTester.ITERATIONS; i++)
        {
            Date date = new Date();

            // Here it is!
            String timeStamp = FormatTester.simpleDateFormat.format(date);

            FormatTester.log.println(timeStamp);
        }
    }
}

The output includes lines like this:
19980607-010650      (correct)
19980607-00010650    (incorrect)
1998000607-010650    (incorrect)
1998060007-00010659  (incorrect)
(Review ID: 33204)
======================================================================

Synchronize on the SimpleDateFormat object.
======================================================================

See also 4101500.
The Format subclasses are not designed to be threadsafe.  Users who require this behavior must synchronize on the format object before using it.  We do not provide synchronization at the subclass granularity in order to allow clients who write subclasses or who use containment designs to provide more efficient synchronization.
 xxxxx@xxxxx  1998-06-09

This is worrisome because the documentation for the class does not say that it
is not thread safe.  Please include a clearly visable note in the documentation
for how to use non-thread safe classes in a thread safe manner.

I agree with gbeck.  While it is well known that 
Swing isn't threadsafe, the format classes lack of
thread safety is not.  More advertising of this
issue should be done.

This problem bit me 9 months later.
The 1.2 documentation still doesn't describe SimpleDateFormat's lack of
thread-safety.
Documentation for each class should include concurrency issues.

Same thing happened to me as jdunning. It sure
would be nice if the javadocs included the 
evaluation comment.

Well we have the same problem !
I have used 20 hours to seek down this problem.
Please clarify in javadoc that it isn't thread-safe