If you find the answer, I'd love to know it, because my phone is having the same kind of trouble.
Garmin will replace your Edge 1000
for $130 if you can't find a better option, by the way. That's a lot after you've already paid for it, but if you don't find a better solution that's what they'll do.