"The wing always stalls at the same AOA" is a simplified telling for student and private pilots. If it was strictly true, then for a given weight and 1G, it would always stall at the same EAS (roughly, IAS) regardless of altitude, and the (low end) barber pole would never move - so your discrepancy wouldn't exist.
But, in a more detailed and advanced look, compressibility (Mach) and viscosity (Reynolds) effects change that - and those values that correspond with higher altitude, reduce the stalling AOA, thus increasing the EAS/IAS stall speed. And that is an actual increase, not just a measurement error.
This is a separate effect from, and not to be confused with, the (much bigger) TAS stall speed increase due to density, that we're all thoroughly familiar with.
https://en.wikipedia.org/wiki/Coffin...(aerodynamics) here is the link fixed