I had a similar incident once. Back in 2005 I took a vacation trip to Paris. Evidently the French immigration agent forgot to stamp my passport on entry into France, and during the boarding passport check the AA gate crew did not want to let me board since they could not find an entry stamp. The frustrating part was that my wife boarded just before me, and they would not let her deplane to help translate what was going on. All the gate agents (and later airport security) folks would tell me is that they thought I snuck into France and therefore could not legally board the aircraft (even though I could produce my boarding pass from DFW-CDG). Obviously it eventually got resolved, though with a bit of frustration and anxiety