I am not sure how the rotation was done but it makes me suspicious. I do know the guy that wants to do it every 3k miles is nuts. At the prices they charge I could just buy a new set every 30k miles or so. If nothing mechanically wrong is found I think my best option is to get one more dismounted rotation and balance and if nothing is wrong with the tire just drive it and watch the results. In hindsight, I should have done what what the owner's manual says and that is just switch the fronts and rears from side to side. I let someone talk me into something that I didn't need.
Even though I don't think it is an issue I will check the lug nuts tomorrow.