diff --git a/src/com/android/exchange/Eas.java b/src/com/android/exchange/Eas.java
index 93ce041..47142bb 100644
--- a/src/com/android/exchange/Eas.java
+++ b/src/com/android/exchange/Eas.java
@@ -21,6 +21,10 @@
 import com.android.emailcommon.service.EmailServiceProxy;
 import com.android.mail.utils.LogUtils;
 
+import java.text.SimpleDateFormat;
+import java.util.Locale;
+import java.util.TimeZone;
+
 /**
  * Constants used throughout the EAS implementation are stored here.
  *
@@ -169,4 +173,11 @@
                 return "Email";
         }
     }
+
+    // Time format documented at http://msdn.microsoft.com/en-us/library/ee201818(v=exchg.80).aspx
+    public static final SimpleDateFormat DATE_FORMAT;
+    static {
+        DATE_FORMAT = new SimpleDateFormat("yyyy-MM-dd'T'HH:mm:ss.S'Z'", Locale.US);
+        DATE_FORMAT.setTimeZone(TimeZone.getTimeZone("UTC"));
+    }
 }
diff --git a/src/com/android/exchange/adapter/ContactsSyncParser.java b/src/com/android/exchange/adapter/ContactsSyncParser.java
index c2bd70c..c5b6068 100644
--- a/src/com/android/exchange/adapter/ContactsSyncParser.java
+++ b/src/com/android/exchange/adapter/ContactsSyncParser.java
@@ -1043,6 +1043,7 @@
             if (cv != null && cvCompareString(cv, Event.START_DATE, birthday)) {
                 return;
             }
+            // TODO: Store the date in the format expected by EAS servers.
             long millis = Utility.parseEmailDateTimeToMillis(birthday);
             GregorianCalendar cal = new GregorianCalendar(TimeZone.getTimeZone("GMT"));
             cal.setTimeInMillis(millis);
diff --git a/src/com/android/exchange/adapter/Search.java b/src/com/android/exchange/adapter/Search.java
index 9f050f2..7fd5452 100644
--- a/src/com/android/exchange/adapter/Search.java
+++ b/src/com/android/exchange/adapter/Search.java
@@ -40,11 +40,7 @@
 
 import java.io.IOException;
 import java.io.InputStream;
-import java.text.SimpleDateFormat;
 import java.util.ArrayList;
-import java.util.Date;
-import java.util.Locale;
-import java.util.TimeZone;
 
 /**
  * Implementation of server-side search for EAS using the EmailService API
@@ -56,14 +52,6 @@
     // The largest number of results we'll ask for per server request
     private static final int MAX_SEARCH_RESULTS = 100;
 
-    // TODO: move this somewhere more unified
-    // Time format documented at http://msdn.microsoft.com/en-us/library/ee201818(v=exchg.80).aspx
-    private static final SimpleDateFormat DATE_FORMAT;
-    static {
-        DATE_FORMAT = new SimpleDateFormat("yyyy-MM-dd'T'HH:mm:ss.S'Z'", Locale.US);
-        DATE_FORMAT.setTimeZone(TimeZone.getTimeZone("UTC"));
-    }
-
     public static int searchMessages(Context context, long accountId, SearchParams searchParams,
             long destMailboxId) {
         // Sanity check for arguments
@@ -110,13 +98,13 @@
             if (searchParams.mStartDate != null) {
                 s.start(Tags.SEARCH_GREATER_THAN);
                 s.tag(Tags.EMAIL_DATE_RECEIVED);
-                s.data(Tags.SEARCH_VALUE, DATE_FORMAT.format(searchParams.mStartDate));
+                s.data(Tags.SEARCH_VALUE, Eas.DATE_FORMAT.format(searchParams.mStartDate));
                 s.end(); // SEARCH_GREATER_THAN
             }
             if (searchParams.mEndDate != null) {
                 s.start(Tags.SEARCH_LESS_THAN);
                 s.tag(Tags.EMAIL_DATE_RECEIVED);
-                s.data(Tags.SEARCH_VALUE, DATE_FORMAT.format(searchParams.mEndDate));
+                s.data(Tags.SEARCH_VALUE, Eas.DATE_FORMAT.format(searchParams.mEndDate));
                 s.end(); // SEARCH_LESS_THAN
             }
             s.end().end();              // SEARCH_AND, SEARCH_QUERY
diff --git a/src/com/android/exchange/service/EasContactsSyncHandler.java b/src/com/android/exchange/service/EasContactsSyncHandler.java
index 0262a03..8757b92 100644
--- a/src/com/android/exchange/service/EasContactsSyncHandler.java
+++ b/src/com/android/exchange/service/EasContactsSyncHandler.java
@@ -41,7 +41,13 @@
 
 import java.io.IOException;
 import java.io.InputStream;
+import java.text.DateFormat;
+import java.text.ParseException;
+import java.text.SimpleDateFormat;
 import java.util.ArrayList;
+import java.util.Date;
+import java.util.Locale;
+import java.util.TimeZone;
 
 /**
  * Performs an Exchange sync for contacts.
@@ -331,6 +337,55 @@
         }
     }
 
+
+    // This is to catch when the contacts provider has a date in this particular wrong format.
+    private static final SimpleDateFormat SHORT_DATE_FORMAT;
+    // Array of formats we check when parsing dates from the contacts provider.
+    private static final DateFormat[] DATE_FORMATS;
+    static {
+        SHORT_DATE_FORMAT = new SimpleDateFormat("yyyy-MM-dd", Locale.US);
+        SHORT_DATE_FORMAT.setTimeZone(TimeZone.getTimeZone("UTC"));
+        //TODO: We only handle two formatting types. The default contacts app will work with this
+        // but any other contacts apps might not. We can try harder to handle those guys too.
+        DATE_FORMATS = new DateFormat[] { Eas.DATE_FORMAT, SHORT_DATE_FORMAT };
+    }
+
+    /**
+     * Helper to add a date to the upsync. It reads the date as a string from the
+     * {@link ContentValues} that we got from the provider, tries to parse it using various formats,
+     * and formats it correctly to send to the server. If it can't parse it, it will omit the date
+     * in the upsync; since Birthdays (the only date currently supported by this class) can be
+     * ghosted, this means that any date changes on the client will NOT be reflected on the server.
+     * @param s The {@link Serializer} for this sync request
+     * @param cv The {@link ContentValues} with the data for this string.
+     * @param column The column name in cv to find the string.
+     * @param tag The tag to use when adding to s.
+     * @throws IOException
+     */
+    private static void sendDateData(final Serializer s, final ContentValues cv,
+            final String column, final int tag) throws IOException {
+        if (cv.containsKey(column)) {
+            final String value = cv.getAsString(column);
+            if (!TextUtils.isEmpty(value)) {
+                Date date;
+                // Check all the formats we know about to see if one of them works.
+                for (final DateFormat format : DATE_FORMATS) {
+                    try {
+                        date = format.parse(value);
+                        if (date != null) {
+                            // We got a legit date for this format, so send it up.
+                            s.data(tag, Eas.DATE_FORMAT.format(date));
+                            return;
+                        }
+                    } catch (final ParseException e) {
+                        // The date didn't match this particular format; keep looping.
+                    }
+                }
+            }
+        }
+    }
+
+
     /**
      * Add a nickname to the upsync.
      * @param s The {@link Serializer} for this sync request.
@@ -576,7 +631,7 @@
      */
     private static void sendBirthday(final Serializer s, final ContentValues cv)
             throws IOException {
-        sendStringData(s, cv, Event.START_DATE, Tags.CONTACTS_BIRTHDAY);
+        sendDateData(s, cv, Event.START_DATE, Tags.CONTACTS_BIRTHDAY);
     }
 
     /**