It is purely a software problem. I can prove this as I have an 8700v that originally was on 4.1 with no issues but upgraded to 4.2 and now seeing them (we have a lot of BlackBerry's here and have seen the same on ones upgraded from 4.2.0 to higher versions and develop the problem).

That being said though I have had a batch of BlackBerry's come from the same provider with the same software on and had some that work fine and others that have an issue every single time you try and use bluetooth so getting it swapped out "might" land you one that is working ok.

I still have not found anyone that actually knows what is causing the problem though (most likely because it is so intermittent and random). So far testing with a couple of different versions of 4.3 on a curve (that has the problems in 4.2.1+) it hasn't had any issues so hopefully it has been fixed (though not seen it officially listed as a fix anywhere).

Working for a company that develops and supports bluetooth products (mainly for BB users) this bug is a massive PITA for me

If you can find it for your BB try upgrading to 4.3, if you have a pearl 4.2.0 has no bluetooth issues but I believe it lacks some fairly useful features that came in later.