Marc,
Next time you try to rust something that is more highly polished, try putting on the first coat or two with a very slightly damp pad. That is, use just as little of the solution as possible. Go over the barrel many times with this very minimally damp pad. Once or twice like this and you should be getting even coverage thereafter. I've done this with a barrel polished to 1000 grit.
If you use less agressive solution, shorter times between boils and less humidity, you will get a more polished blue - if you start with more polished metal. It will take more applications however.
I'm no expert either but I have been doing a fair bit of blueing as I enjoy it for some reason.
Brent