Revision history [back]

First, get fx and fy nailed down - as long as they are moving around, cx and cy won't be consistent. Some things i've tried to get good results on bad cameras:

Did you use the program in the Code examples or roll your own? If you programmed your own, use the example program to make sure you are getting EXACTLY the same numbers and error values in yours before trusting it.
Turn off Auto focus and zoom - they will both mess with the physical focal length and vary fx and fy.
Use lots of samples - I think the books say 10 as a minimum. Use at least 20, I've used as many as 100.
Make sure that your chessboard is rigid - tape it tightly to some wood or cardboard - if it's wrinkled or flopping around it will affect calibration.
Do you have a proper chessboard? - the book says the chessboard should be at least several corners in each direction - and that one dimension should have an odd number of corners and the other should be even. I use a 9 X 6 corner chessboard printed on a 8 1/2 X 11 sheet of paper taped to some cardboard.
Make sure your chessboard is taking up as much of the camera view as possible - especially with your low resolution. Don't be afraid to rotate and skew, but when you do make it big - remember you only need inside corners within the camera frame. (not having smaller sectional views might affect the distortion correction numbers - but your basic matrix is probably the first step.)
Finally, use the drawChessboardCorners function (or use the Example Code program's show chessboards option) to pop-up the chessboard-by-chessboard results. Take a close look at where OpenCV thinks the corners are. With low-res video stills I've seen chessboards that OpenCV thinks are good where the corners are drawn 1/2 square off where they should be. Don't use bad corners in your calibration.

Good Luck!