What kind of tooling were you using? IMO, deadlocks are some of the easiest concurrency bugs to diagnose. If you can see the thread stacks, it is easy to see threads are blocked from acquiring a lock. If you can attach a debugger, it is easy to see which locks are involved. Then you can pretty much figure things out using the straightforward guideline that if multiple locks are involved, they must be acquired in the same order in all code paths.
I don't want to devalue your experience, but I am surprised to hear that. Livelock is harder to debug. Silent data corruption caused by missing or wrong synchronization is way harder to debug.