Setting the page's Culture to Russian didn't work. A quick Reflectoring showed that ObjectDataSource uses InvariantCulture for parsing the supplied values.
The solution is sort of ugly: use the grid's Updating event and swap the string with the corresponding date:
Protected Sub gridDjSchedules_RowUpdating(ByVal sender As Object, ByVal e As System.Web.UI.WebControls.GridViewUpdateEventArgs)
e.NewValues("TheDate") = Convert.ToDateTime(e.NewValues("TheDate"), System.Globalization.CultureInfo.CurrentCulture)
Looks like it's time to create a custom control..