Is it possible to just connect with it just with bluetooth? So without a 3rd party application? Not that this will solve the problem, but it could give you some information about wether the gps is compatible with the SGS. Don't know if it's possible that certain bluetooth gps receivers won't connect because of incompatibility, but it wouldn't surprise me.
But the first step in solving this problem, I first would check if I can just establish a simple bluetooth connection with the device.
Next, when connecting, keep your internal GPS on at all times. When you begin navigating, you can disable it.