Message Timestamps not localized for all languages

We are currently using DateUtils to create the timestamp strings for messages/posts/statuses. Unfortunately the languages supported by it varies greatly across APIs.
I wrote a test application which dumps the strings for all our languages (fallback means it's falling back to the system language):

API	15 - 16	17 - 19	21 - 22	23	24 - 25	26 - 28
Failed	br (fallback) eu (fallback) gl (fallback) ms (fallback) oc (fallback) sq (fallback)	br (fallback) eu (fallback) gl (fallback) he (fallback) ms (fallback) oc (fallback) sq (fallback)	ast (fallback) br (fallback) eu (fallback) fa (fallback) gl(fallback) he (fallback) ms (fallback) oc (fallback) sq (fallback)	ast br oc	ast oc	oc