The design of java.util.Calendar is deeply flawed. The class combines two separate representations of time (a simple linear time stamp as well as a calendar-based multi-field representation) with the mapping algorithms between these two representations. The two representations are not continuously kept in sync, but only resynched as a side effect of several method calls, including some where this is rather unexpected (see bug 4340146).

The class should be replaced with two separate classes/interfaces that encapsulate either state or mapping. CalendarDate would encapsulate a calendar-dependent representation of a point in time using multiple fields - similar to the fields of the current Calendar class. CalendarSystem (since the better name Calendar has been taken) encapsulates a mapping between Date and CalendarDate, including methods  that manipulate a CalendarDate in calendar-specific ways (say, adding a month).

Taking the current Calendar class, public/protected members could go to the two new classes/interfaces as follows:

CalendarDate: all constants, clear, clone, equals, get, hashCode, set, toString

CalendarSystem: mapToCalendarDate (replaces computeFields, setTime, setTimeInMillis), mapFromCalendarDate (replaces computeTime, getTime, getTimeInMillis), add, clone, equals, getActualMaximum, getActualMinimum, getAvailableLocales, getFirstDayOfWeek, getGreatestMaximum, getGreatestMinimum, getInstance, getLeastMaximum, getMaximum, getMinimalDaysInFirstWeek, getMinimum, getTimeZone (?), hashCode, isLenient, roll, setFirstDayOfWeek, setLenient, setMinimalDaysInFirstWeek, setTimeZone, toString

neither: areFieldsSet, "fields" field, isSet, isTimeSet, time, after, before, complete, computeFields, computeTime, getTime, getTimeInMillis, internalGet, isSet

It might be possible to define CalendarSystem is an interface, and then reimplement Calendar as "extends CalendarDate implements CalendarSystem".

Calendar and GregorianCalendar should be deprecated. All methods referring to them should either be deprecated or be changed to refer to CalendarDate or CalendarSystem.

It's not clear whether a public replacement for GregorianCalendar is needed. Applications should never rely on a specific calendar, but a public class may be useful for pluggable locales.
CR description from 6193609:

I would like to nominate Joda Time (found here: http://joda-time.sourceforge.net/userguide.html) for review by Sun. It seems to provide a rich and extensive replacement for Date and Calendar and replacing those two is certainly well-warranted.

This has been discussed in this discussion forum: http://forums.java.net/jive/thread.jspa?threadID=198&tstart=0