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.