New Cyanotype is very sensitive to paper, and gelatine sizing will not help.
I second the Weston doploma... I tried once the first batch when the paper was newly announced, and it worked beautifully. (New Cyanotype is my way of testing paper: if this process works, others will also.)
You may bring a range of other papers into service, however, by pre-coating them with citric acid (try a 40% solution).