With MBR (master boot record) partitioning, Windows had to be on a primary partition, and it was only possible to have four of them. Linux could be installed to a primary or extended partition, of which there could be more.
As far as I know the order never actually mattered as long as Windows could have a primary partition. The newer GPT system doesn't have such a distinction or low limits (Windows is limited to 128 partitions per disk; I think Linux can handle more).
One question - did you shrink partition from the front, or from the back of the disk?
Usually Windows has to be in front of the Linux, so if it's from the back, I'd really have to try that!