My iBook had the same problem. It turns out that the keyboard, which has a thin metal frame on the bottom side, was actually bent.
Take your keyboard, set it on the palm rest upside down as the manual instructs in the removal procedure, and place a light, relatively flat object on it (I used a DVD case). Look to see if there's an inconsistent gap between the flat object and the back of the keyboard - my keyboard was clearly bent on the right side by several millimeters. It was easy to straighten it out, and now my keyboard is as solid on the right as it is on the left.