Key violation: unknown or no key involved

I have a Delphi app running on multiple computers on a network with BDE
accessing a paradox database.  I had to fix an "Index out of date"
error.  I did that be blowing away the indexes of the offending datafile
and rebuilding them.  I now have "Key violation: unknown or not key

All of the indexes that should be there for that .DB file are present.
What can cause this error? Help! Thanks.