Some pure speculation... Michaels sells mostly low to mid quality products to a customer base that is price sensitive. In that market, manufacturers may change product specifications to meet a price point without changing the product name. In other words, you'll never be sure what you got is the same as what was previously tested. This is, to my mind, a good reason to stick to the better grades of paper.
I've recently tried a bunch of papers and will, when time permits, make a post about them. However, one I will recommend off the top of my head is Stonehenge Light... very reasonably priced, 100% cotton and works well as it comes for traditional cyanotypes. It is fairly lightweight at 135 gsm but for small prints it works. The heavier (250 gsm) Stonehenge papers also work well and are reasonably priced. I'm partial to the "warm" version, but also use the "white".
Another thought... get yourself a real brush. Foam brushes have their place, but they are not the best tool for hand coating paper in my experience. The quality of foam brushes is all over the place. Some are very coarse and abrasive and are not suited at all for coating paper. Others work just fine. These also, are sold in a very price sensitive market and the suppliers are not consistent in what they provide... you might get a brush that is well suited but the next one you buy even from the same store, may well be very different.