I remember that an engineer we tried to hire at Google in 2000 turned down the offer for the same reason -- he thought that all of the interesting problems were probably already solved :)
The reality is typically the opposite. Most startups are technically straightforward to start with and only get really advanced with scale.