Something similar happened at Las Vegas. My friend was flying Southwest, and the person checking the boarding passes told her that her carry on was too large (which was fine on the trip out on Southwest as carryon). We had to rush down to Southwest curb check-in and run back to the security line to check in.

Ah, the wonderful smell of airport hassles...