If your lens has anything like a flat field of focus (that is, if you can shoot a brick wall and the bricks in the corner are almost† as sharp as the bricks in the centre), then focus-and-recompose except at telephoto-class angles of view is going to result in some amount of focus error. You aren't focusing according to the distance between the camera and the subject, but on the distance between the film/sensor plane and the subject. When you focus then recompose, you are changing the angle of the sensor plane, and so you are changing the distance between the sensor plane and the subject.

In this exaggerated example, you move the camera to focus on the subject at the centre of the frame and everything looks hunky and dory. But when you recompose, your focus point lies on the red line, which is now behind the subject. The wider your lens and the further from centre your subject is in the final composition, the worse this gets. With very long lenses and subjects that are not too very close, you'd hardly notice, but on a standard lens or wider it really gets to be a problem.

Somewhat counterintuitively, "badly corrected" lenses are going to be better-behaved in a focus-and-recompose scenario than "high quality" lenses. Their spherical field of focus means that you are more likely to be closer to being in focus after recomposing -- even if the brick wall shot looks horrible at the corners.

If you have other autofocus sensors available that are closer to where the subject is going to be in the final image, use them instead. The less you can move the camera between focusing and shooting, the better.

† I say almost because very few lenses, even those with very flat fields, can focus obliquely as well as they can focus normally, so some amount of corner softening is the usual case.