RFC822 does not allow a colon to be in the time zone portion of date. It expects just the 4 digits. The name of that Dojo method indicates that it is using RFC3339. It seems that is practically the same format as ISO8601ISO8601. It just so happens that Joda Time has ISODateTimeFormat which is ISO8601 compatible if you are able to use that library. The method dateTimeNoMillis() looks like a match with the Dojo format. It really is nicer than the standard Java date and time API. Otherwise highlycaffeinated's suggestion would be the way to go.
Updated in response to Jamen's update
Isn't there a way to have Dojo use a format that doesn't include the timezone? Then you can adjust the format on the Java side to match. I don't know much about Dojo and I haven't been able to find any documentation on the toRfc3339 function it provides.