Had a similar experiance with Czech Airlines flying from Venice to Prague several years ago. Had flown in and out of several European ports - not a problem until check-in with Czech .Cost us about 150 Euro ! No further problems after that in Eurpoe or Nth America.One wonders !