It seems like a relatively common mistake is to assume that the java.text.SimpleDateFormat class is thread-safe (at least for methods such as format(), which you might not expect to mutate state!). This is not true; SimpleDateFormat is not thread-safe, and format() does mutate state. From the javadoc:

Date formats are not synchronized. It is recommended to create separate format instances for each thread. If multiple threads access a format concurrently, it must be synchronized externally.

Suggestions on handling synchronization:

• Use the Joda Time libraries if possible. They are thread safe. Joda Time is fairly easy to port to from existing JDK compatible code.
• Synchronize calls to format() manually. You probably want to write a wrapper class/function to do this, and make sure nobody calls the original format() method by accident. This seems like it should be safe, but see http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=422833.
• Use thread-local storage, e.g.

private final static ThreadLocal<SimpleDateFormat> shortTimeFormat =
     new ThreadLocal<SimpleDateFormat>() {
            protected SimpleDateFormat initialValue() {
                 return new SimpleDateFormat("HH:mm");
             }
      };

N.B. In general, you should be very careful when using ThreadLocal storage, especially when using thread pools (your data won’t be automatically garbage collected and may be visible to other Threads—a security risk) or when storing references to Thread objects in ThreadLocal storage (which might confuse the GC). However, in this case, we should be okay.