hehe if the wheel was infact put on straight and its actually smacking the frame (not the brake pads) i think urr tire is a little more than slightly outta true. thats an awfully big wobble to hit the frame. urr wheel is prolly on an angle just loosen the bolt or quick release and straighten.
If the worked on the bottom bracket only, they probably did not remove or even touch the rear wheel at all. However, a good shop would give a bike a look over during the ticket writing and point out an obvious problem...and then ask if you wanted it repaired.