You need to reset the toilet again. This time, set it in place without the new wax ring, and shim it so it doesn't rock. Pick it up, then install it with the new wax ring, and bolt it down.
You can use composite tapered shims, or I tend to use coins. The coins don't rust, and you don't have to go to the store to buy them. Anywhere from a dime to a penny or nickel will give you three different thicknesses that fix most of them, unless the floor is really out of whack where a tapered shim works much better.
If a toilet rocks, it will break the wax seal...the wax isn't like a rubber seal that will rebound. Once you've rocked it, it compresses, and then it rocks back, and now you have an opening in the wax. The wax is only to make the seal, neither it nor the bolts will keep the toilet from rocking. If you try with the bolts, you'll probably break the toilet.