No, there is no workaround to make SimpleDateFormat understand this format without preprocessing the string (for example by removing the : from the string). (edit: except if you're using Java 7 or newer as noted by assylias).
It looks like you're trying to parse strings in the standard XML format for dates and times (ISO 8601). I would recommend using the Joda Time library which has support for this format.
If you can't or don't want to use Joda Time for some reason, then you can use classes from the package javax.xml.datatype to parse and format timestamps in this format. For example:
DatatypeFactory factory = DatatypeFactory.newInstance();
// Parses a string in ISO 8601 format to an XMLGregorianCalendar
XMLGregorianCalendar xmlCal = factory.newXMLGregorianCalendar("2012-05-16T10:39:00+03:00");
// Convert it to a regular java.util.Calendar
Calendar cal = xmlCal.toGregorianCalendar();