Tom
Bob- the toilet should not rock, period.
The new tile – how thick 1/4″ or more?
On concrete or wood floor?
If the toilet rocks, call the tile contractor and complain that the new floor is not level. (Unless of course you are using Mexican tile, Saltillo or other which is always uneven.)
While I hate to shim toilets, I have done it using either brass or plastic. The trick is to get the shim under that appropriate spot with enough width that even if it moves it will still support the narrow toilet edge. Good luck.
