Complexity is a property of the problem; complication is a property of the solution. Whilst over-complication is bad (e.g. your Rube Goldberg example), so is being simplistic (not enough complications to handle the complexity).
Examples of simplistic solutions can be found in all of those "What programmers don't know about FOO" articles (human names, timezones, distributed systems, etc.)
I haven't thought too much about how such things relate, but my first thought is that TDD seems biased towards oversimplification, since we do 'the simplest thing which makes the tests pass'. If we're testing that Bob's user profile shows the name "Bob", then the simplest thing is to have all profiles hard-coded to say "Bob". To fix this, TDD tells us to add more tests which check different names. That's before we've even begun to consider the hairy details of how names are used in different cultures.
It's a reasonable approach, but it's not "solving" the oversimplification problem, it's just shifting it into the test suite. It's similar to the problem of over-fitting in machine learning models, where we may need millions of input/output examples to narrow-down the intended behaviour.
I think the aggressive refactoring advocated by TDD manages to bias it away from overcomplication.
At some point you need to specify which edge cases you need.
As I said, it doesn't solve the problem of overcomplication/simplification, it just shifts the burden on to the test suite instead of the program.
Complicated to me means that complications have been added where they weren’t needed. A Rube Goldberg machine solves a simple problem that has been complicated.