I've debugged my fair shared of parallel programs (multithreaded and distributed), and I've used a mix of both techniques. The advantage to print statements is that it gives you an execution trace. It's easier for me to reconstruct the sequence of events - which is not trivial in a parallel program. What I give up is full knowledge of any one instant. And that's what a debugger gives me.

It's a trade-off, but I usually start with traces.