This is what worked on my laptop with one drive: I installed Fedora. Before rebooting I used GParted to resize the disk creating space for a Windows partition. After that I rebooted and installed Windows on the new empty partition. Done.
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!
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).