Just to make shure: I have printed a few of my negs in print-out palladium (with a little sodium platinate added as a contrast agent and as palladium-toned kallitypes, and I would not be able to tell the difference if I wouldn't know. You should be able to get the same tonality and sharpness.
It is difficult to see where the problem might be without knowing all the variables. For instance, I have never printed on Stonehenge rising paper, because it is not commonly available here, but I know of course that it is frequently mentioned as a good pat/pd paper. (batches of paper change, however.)
From the top of my hat I would suggest the following testing procedure: coat as you used to, let the coating sit for a minute or so, then dry the paper as fast and as dry as possible; I suggest use a hair dryer. Contrary to what is written elsewhere, I would yet have to experience the first fogging from heat drying. Just don't overdo the heat, but get the paper bone-dry. Expose immediately, develop immediately (5 min); the printout should be alltogether faint, without darker rust-colored shadows.
Also, and I risk becoming a bit one-sided here, because I have just written far and wide about papers in another thread, but place a piece of your paper in a 1% acid, and see if some bubbles start appearing (no real fizzing or so, just some bubbles, and maybe a very faint sound). If this happens, your paper has an alkaline buffer which might also create the problem.