I love rust, but the entire system of tracking lifetimes is both a major upside and a downside. When it "just works", it's like a dream where you can make a mess and have it cleaned up automatically, cheaply, and at exactly the right time. When you start getting errors or want to refactor across function call boundaries, it can be frustrating and/or require a quite deep understanding of the workings of the system to figure out how to fix it.
tl;dr: If you consider "has a fairly complex concept that is unfamiliar and necessary to learn with a fair degree of depth" a downside, then I think it has one.
I somewhat agree with your characterization. Lifetimes definitely adds a bit of complexity to the language. And you're right about the benefit; lifetimes are frankly awesome. It's really really cool to write memory safe code without using a GC.
When I first started with Rust (was also my first foray with lifetimes), the compiler completely kicked my ass for at least a few days. I struggled a lot with writing anything beyond a few functions, and especially when those functions were returning borrowed pointers. I think the code I wrote at the point could be fairly characterized as, "the bare minimum that I could convince the compiler to accept."
But as I wrote more code, I got better at it pretty quickly. At this point, I can look at most Rust code and feel pretty good about spotting lifetime errors before consulting the compiler. I'd say it only took me a couple thousand lines of code to get there, which isn't a huge price to pay.
Anyway, this is obviously a personal anecdote. But it's coming from someone who thought Rust was crazy complex only a few months ago. FWIW, it took me about 48 days from knowing absolutely zero Rust (other than random Internet buzz) to writing and getting libregex merged upstream.
We're in violent agreement. (Though you've gone much further with rust more quickly than I - libregex is beautiful.) A couple thousand lines to feel pretty solid with lifetimes sounds about right - I'm getting close to that range and the issues I'm hitting are increasingly of the obscure kind rather than the initial "nothing works, I guess I'll put it all on the heap!" kind.
This is basically why I said if you consider this a downside. I think it's only a "downside" in the same way that purity is a "downside" in Haskell - it isn't accidental complexity, and wrapping your head around it is just a part of really learning the language.
tl;dr: If you consider "has a fairly complex concept that is unfamiliar and necessary to learn with a fair degree of depth" a downside, then I think it has one.