I recommend taking the leftover scale and paint off mechanically before priming. You can use a drill with a Scotch Pad (sold at your local hardware or home store) to do the stripping. The same company, 3M, also makes one you can use on an angle grinder (my favorite method).
Then, treat your rust with a phosphoric treatment (Such as Boeshield Rust Free) to retard further corrosion. After that, go ahead and prime your frame.
Rustoleum is OK, but I have been frustrated with the cans gumming up with about 30% of the product left inside. The crucial step is to follow with a primer sealer, then paint. We used the phosphoric treatment with great success in the swimming pool industry on steel products that were continuously immersed in a relatively corrosive pool solution.
Good luck,
