We ran into this issue in our very large production environment.  We created a VF web-to-case form, which supports 10+ languages via custom labels and the translation workbench.

The form inserts a case, and that insert triggers a Case AfterInsert trigger that takes the SuppliedEmail and SuppliedName fields to create or associate a proper Contact to the Case.

When submitting this form in any language BUT English, the follow exception is thrown:

System.QueryException: Non-selective query against large object type (more than 100000 rows). Consider an indexed filter or contact salesforce.com about custom indexing.
Even if a field is indexed a filter might still not be selective when:

1. The filter value includes null (for instance binding with a list that contains null)

2. Data skew exists whereby the number of matching rows is very large (for instance, filtering for a particular foreign key value that occurs many times) 

None of the fields involved in this form or trigger are causing this, as I'm entering the same exact data in the English form as I am the Japanese form.

I logged a Case with support for this, but we're in a time crunch and I'd rather not have to settle with wrapping a trigger in a useless try...catch block to bypass this issue, and subsequently defeat the purpose of the trigger in this use case.

Again, this is only when the VF page language attribute is not English, and all SOQL queries use a "limit 1" statement, on top of ruling out nulls.