With computers and laptops, that would be a yes. You can connect multiple bluetooth devices into a single unit...similar to how USB connects.
With cell phones, they can work as well...but with lower processing power, they may 'slow' down as more devices you connect into. But, with one or two devices, they shouldn't have a problem. So with your example of a headset and GPS, you should be fine.
As every cell phone is different, there may be an issue, so don't be suprised if it doesn't work at the same time. So, agian, in theory, it should work.
Hope that this helps, and good luck
I have a Blackberry 8700 and a bluetooth headset for hands-free. I just bought a GPS receiver that works with the Blackberry via bluetooth. Can I use both devices at the same time or can you use only one bluetooth device at a time? Thanks.