Yes, I get this problem too!
I've posted eleswhere on this forum about it, but got no answer as yet. I'm using Plantronics Backbeat headphones, and thought they were just 'losing touch' with the SGS randomly, but since reading your post, I find they work fine until I use the GPS & then voila - no bluetooth connection to the headset anymore. The GPS in my SGS also works fine, BTW, unlike many others, by the sound of it.
Unfortunately, while I can commiserate (& feel a little happier knowing what's causing the Bluetooth 'drop-out'), I can't offer any solution, as I'm not by any stretch of the imagination a coder/programmer. Sorry.