API Lookup Field Criteria Broken

When selecting a record to edit using a lookup field value, all I got was "Failure, No Records Found With Specified Criteria.". I've double/triple/quadrupal checked my lookup field name. Adding records via the API with the lookup field name and criteria value is fine.