The locale problem only affects the speed once it decides to use an index; it does not affect whether it chooses an index or sequential scan. Try doing a VACUUM ANALYZE; that often makes it start using index scans.
pgsql-general by date:
Соглашаюсь с условиями обработки персональных данных