"I am using the EFS 18-135 that came with the camera"
This is most of your problem. It is too slow. 
Way too slow, as a f2.8 constant aperture or faster is really what you want. A camera can do only so much with what it is given. Than you need to increase the light either artifically (flash, etc) or faster lenses (f2.8 or lower nimber).
