How to display translated term names in exposed form in block
Your best path would be to open an issue with Views after confirming that the terms don't translate correctly with BEF module disabled.

I found this issue related to translation in BEF's queue, but that looks to be slightly different or only part of your issue.

Unfortunately it can be difficult for contrib module maintainers to test their modules in multiple languages unless they happen to run their own multilingual site, so it is up to the community to make them aware of issues and help test patches.

You also might want to take a look at http://drupal.org/project/i18nviews