I've used Ospho on many projects, but never used bed liner. When Ospho dries it forms a chalky residue on the surface. I usually just hit it with a very quick sand blast. Ospho is phosphoric acid that replaces the oxygen in the rust with phosphorus. The advantage of using Opsho even if you blast it later is that you do not have to blast to shiny metal to kill the rust. If you do not have a sand blaster, a wire brush should work as well.
With the surface residue removed, I don't see why the bed liner won't stick.