I'm not entirely sure when this started, but it must be in between php 5.3.2 and 5.5.0. Anyway, the thing is php will now output a notice when strtr is called with multidimensional $replace_pairs array, even if the array entries are not used.
And this is precisely what occurs in includes/sessions.php, where format_date will call strtr with one array in the $date_cache[$format]['lang'] entry (the AGO key).
From my experience, the result is not altered, strtr works just as before, but throws a notice on recent versions.
Replacing strtr with @strtr seems a working solution.