I haven't been able to have the strings show up properly translated on the admin screen but the emails sent out when I update the status are correctly translated.

I think the strings you see in the drop-down list are fetched from the database which is what makes it next to impossible to translate them without a major code rewrite.