I used to have a Motorola e815 cell phone. Worked flawlessly, connected automatically, ect. Now I have a Verizon XV6800 pda phone (Same as the Sprint Mogul). I doesn't automatically connect and it randomly works. Anyone else having issues?
I had the same problem and I found the solution, hopefully this will work for you too.
My Blackberry used to work perfectly, Bluetooth would always stay "on" and "discoverable" on the phone, so there were no problems having MyGIG connect to it. However, once I bought an HTC TyTN (with Windows Mobile v5) Bluetooth would randomly disconnect, or at least turn "discoverable" off. After much Googling and trial and error, I found that upgrading the TyTN to Windows Mobile v6 cured it.
If that is not an option for you, try installing a little program called "Bandswitch". It lets you enable or diable Bluetooth, and this program will make sure it stays that way until you change it.
Hope this helps!! Let us know how it goes.