I get the same problem w/ my storm 1. After the Summer 2009 software update, the bluetooth connection was perfect. Then, the Oct 2009 software update came out, sped up the phone quite a bit, but killed the previously-fixed bluetooth problem.
Sorry to say - there's no fix for it right now. We'll just have to wait for RIM to get off their lunch break and finish the next upgrade.