I've used auto-straighten successfully for year, but suddenly it's unable to straighten an obvious horizon. I just did a family portrait shoot on the beach and there's a clear horizon where the water meets the sky in almost every shot. When I hit Auto in the Crop tool, not only does it fail to straighten the horizon, it actually goes the OTHER way and makes things worse than they were!
Without seeing an example of the photos, we can only guess. Remember that Lightroom simply looks for lines, either horizontal lines or vertical lines. Maybe there is a clear vertical line, like a flag pole or something like that, that confuses Lightroom.