In 737 case, it means redesign of the landing gear system, fuselage modifications, recertification, retraining, new support system requirements eg. Higher stairs, cargo support equipment etc.

You also can't put longer main gear: as they fold inward, they have to attached at points separated by over twice the height. If you move them apart, you have to make the center fuselage as well as the root of the wings much stronger. That's a much bigger change than anything else.

I believe they altered the landing gear so it extends upon deployment, giving it a bit more height, but that's not enough. They can't just put longer legs, there isn't enough room. There's stuff there (cables, devices, bulkheads ...) and moving them requires a significant redesign. For the main gears, they would have to be attached further away from the center lest they bump into each other, which means the wings and fuselage would have to be stronger to accommodate for it. Very quickly you're just designing a new plane.

What about telescoping landing gear?

The thing is, this wouldn't have magically solved the issue. Larger engines hanging from your wing fundamentally affect the balance of an airplane. Take the thrust vector for example. The further you move the engine from the longitudinal axis of the plane, the stronger the angular momentum is, that is exercised from the engines onto the plane, especially when pitching up.

Taller landing gear makes loading the plane (especially with luggage) much harder.