Which would improve image quality more, lens or camera body?

I have the Rebel 1000D xs camera.  Not sure if it's the camera, photographer (me) or unrealistic expectations but I've never been impressed with pixel level detail of the camera and the kit lens.  I was wondering for roughly the same price, which upgrade would provide better image quality, upgrading to a T4i with kit lens or investing in the Canon EFS 15-85 lens?  Also is there a difference in optical quality between the 18-55 kit lens that came with my Rebel 1000D and the one that comes with the T4i?