Points to ponder:
*Paper - the paper you're using may not be appropriate to the process. Papers with a lot of buffering agents in them can cause all sorts of problems. Sizing may also be an issue. Papers that are too heavily sized may not allow enough sensitizer to soak in.
*Exposure - Cyanotypes need a lot of exposure. They're not properly exposed until the image starts to reverse a bit. Even in direct sun here in the desert southwest my exposures run anywhere from 10 to 15 minutes (sometimes less depending on the neg). Underexposed prints will essentially wash away (they might look fine for a moment or two but then - woosh, gone).
BTW, are you using a split back printing frame? If not, I'd highly recommend one. It's much easier to check exposure with a split back frame. For my first print of the day I lay my print out (in the frame) and start my stopwatch. I then expose by inspection, checking the progress (and pausing the stopwatch) at several points until it looks "about right". I note the total exposure time and then process the print. Depending on the outcome I may adjust my final printing time up or down as necessary. Additional prints from the same negative that day get exposed using the time I recording during the test (with any adjustments I may have deemed necessary). The procedure is the same (just a bit more lengthy) if I expose in my UV box.