It seems like a barrel problem to me. Before replacing the barrel, check the barrel mounting bolts to see if they're tight. If they are and you can't see any bad spots in a clean barrel, you may want to send the rifle back to Ruger for repair.
Other things to check:
Loosen the stock/action bolt and see how the action fits in the stock by moving the barrel side to side. If it's really loose, try using strips of electrical tape on each side of the receiver to make it fit tighter. I did this as a test on a friend's rifle and he started winning plinker benchrest matches with his and wouldn't let me glassbed it.
Check the mount base screws. It doesn't hurt to use Locktite both on the screw threads and under the base.
If all that is okay, consider removing the barrel and using high-strength Loctite/Permatex Sleeve Retainer/Stud and Bearing Mount to stabilize the barrel in the receiver. It makes a significant difference, but won't make a bad barrel better. (Consider getting an after-market Green Mtn., or other good barrel before Loctiting it in.) If you Locktite a barrel in, it can still be removed by heating the receiver to about 250*f and the Locktite will melt. That shouldn't hurt the metal, but might singe receiver paint if a torch is used.
Good luck!