I would expect data corruption - e.g. if you're parsing two dates at the same time, you could have one call polluted by data from another.
It's easy to imagine how this could happen: parsing often involves maintaining a certain amount of state as to what you've read so far. If two threads are both trampling on the same state, you'll get problems. For example, DateFormat exposes a calendar field of type Calendar, and looking at the code of SimpleDateFormat, some methods call calendar.set(...) and others call calendar.get(...). This is clearly not thread-safe.
I haven't looked into the exact details of why DateFormat isn't thread-safe, but for me it's enough to know that it is unsafe without synchronization - the exact manners of non-safety could even change between releases.
Personally I would use the parsers from Joda Time instead, as they are thread safe - and Joda Time is a much better date and time API to start with :)