Well, first of all: what GC are you talking about?
The Java7 default (Concurrent Mark And Sweep, IIRC) will try to work concurrently, but it may still stop the world if it can not find a suitable situation in all threads. This is particularly nasty with for loops which can not be interrupted. At least this is how I understood things. Take it with a grain of salt. The new G1 has some improvements for this situation.
Knowledge taken from the back of my head where it was pushed by a talk from some Azul guy a few years back