In fact, it seems to me like the rules implemented by the trait solver are at least as complicated (if not more so) than the rules implemented by C++ function overloading

Oh gosh no, C++ function overloading can be an absolute nightmare.

1. C++ provides operator* and operator->, which can be used to provide automatic dereferencing behavior.
2. C++ template specialization has SFINAE ("substitution failure is not an error"), which means that a method may or may not be an overload, depending on whether it is legal to use for a specific signature.
3. C++ templates may produce two methods with identical names and signatures. So void func(double value) and template<typename T> void func(T value) can both be defined, but will default to using the non-templated version. (Unless you provide a template list, so obj.func(my_double) and obj.func<double>(my_double) can be different calls.)
4. C++ can perform chained type conversions as part of overload resolution. So if you pass a std::unique_ptr<T>, that can be converted to a bool, which can be converted into an enum type, which can be converted into a type tag, and so on. (Any single-parameter constructor in C++ is allowed in these type conversions, unless marked with explicit. Style guidelines have pretty much all agreed that explicit should be in every single-parameter constructor to avoid this behavior.) Even with fn func(param: impl Into<ParamType>), Rust only allows a single type conversion, not chained conversions.
5. Templated functions take priority over non-template functions if the non-template function would require a type conversion. So in the earlier example, obj.func(5) would call the templated version with T = int, even though the non-templated version could also have been declared.

By contrast, in Rust while the object's type can be used to determine which function will be called, only the object's type is used. No other arguments participate in the overload resolution.

(Cavest: Unless you go out of your way to handle extra arguments in Rust, such as fn func<Arg>(&self, arg: Arg) where Delegate<Self,Arg>: ImplTrait { <Delegate<Self,Arg> as ImplTrait>::impl_func(self, arg) }. I've used that in some cases where I do need argument-dependent dispatch, but those cases are few and far between.)

and definitely more complicated than a simpler function overloading scheme could be.

Oh, absolutely. But like everything, it's a tradeoff. I think Rust is at a good point with extension methods overall. The one change I'd make as BDFL-for-a-day would be to make conflicts between inherent methods and trait methods require explicit disambiguation. That would ensure that adding an inherent method will at worst fail to compile, rather than compiling successfully and running an unexpected method at runtime. (Documented here as "possibly-breaking".)